make function with 'if' point-free

13
votes

I have a task in Haskell (no, it's not my homework, I'm learning for exam).

The task is:

Write point-free function numocc which counts occurrences of element in given lists. For example: numocc 1 [[1, 2], [2, 3, 2, 1, 1], [3]] = [1, 2, 0]

This is my code:

addif :: Eq a => a -> Int -> a -> Int
addif x acc y = if x == y then acc+1 else acc

count :: Eq a => a -> [a] -> Int
count = flip foldl 0 . addif

numocc :: Eq a => a -> [[a]] -> [Int]
numocc = map . count

numocc and count are 'point-free', but they are using function addif which isn't.

I have no idea how can I do the function addif point-free. Is there any way to do if statement point-free? Maybe there is a trick which use no if?

6
haskellfunctional-programmingpointfree
are you allowed to do math-chenigans like ` let f x y = 1 - ceiling (fromIntegral (x-y) / fromIntegral y) :: Int`? (which is not exactly what you need ;)) - Random Dev
but 1 - ceiling (abs $ fromIntegral (x-y) / fromIntegral (max x y)) :: Int should do it if I did not miss some nasty border case somewhere - maybe you will want to reason about it or run some quickchecks ;) (well I missed some negatives so you'll have to but more abs in ... but the principle should be obvious ... the real solution is trivial and left for the reader :D) - Random Dev
In general you can replace an if statement with the function bool :: Bool -> a -> a -> a; bool False f _ = f; bool True _ t = t, in which case you can always form a "normal" expression that can be made point free with the regular methods. - user2407038

6 Answers

10
votes

I would use the fact that you can easily convert a Bool to an Int using fromEnum:

addif x acc y = acc + fromEnum (x == y)

Now you can start applying the usual tricks to make it point-free

-- Go prefix and use $
addif x acc y = (+) acc $ fromEnum $ (==) x y
-- Swap $ for . when dropping the last argument
addif x acc = (+) acc . fromEnum . (==) x

And so on. I won't take away all the fun of making it point free, especially when there's tools to do it for you.

Alternatively, you could write a function like

count x = sum . map (fromEnum . (==) x)

Which is almost point free, and there are tricks that get you closer, although they get pretty nasty quickly:

count = fmap fmap fmap sum map . fmap fmap fmap fromEnum (==)

Here I think it actually looks nicer to use fmap instead of (.), although you could replace every fmap with (.) and it would be the exact same code. Essentially, the (fmap fmap fmap) composes a single argument and a two argument function together, if you instead give it the name .: you could write this as

count = (sum .: map) . (fromEnum .: (==))

Broken down:

> :t fmap fmap fmap sum map
Num a => (a -> b) -> [a] -> b

So it takes a function from b to a numeric a, a list of bs, and returns an a, not too bad.

> :t fmap fmap fmap fromEnum (==)
Eq a => a -> a -> Int

And this type can be written as Eq a => a -> (a -> Int), which is an important thing to note. That makes this function's return type match the input to fmap fmap fmap sum map with b ~ Int, so we can compose them to get a function of type Eq a => a -> [a] -> Int.

8
votes

why not

numocc x 
  = map (length . filter (== x))
  = map ((length .) (filter (== x)) )
  = map (((length .) . filter) (== x))
  = map (((length .) . filter) ((==) x))
  = map (((length .) . filter . (==)) x)
  = (map . ((length .) . filter . (==))) x
  = (map . (length .) . filter . (==)) x

and then the trivial eta-contraction.

6
votes

One trick would be to import one of the many if functions, e.g. Data.Bool.bool 1 0 (also found in Data.Bool.Extras).

A more arcane trick would be to use Foreign.Marshal.Utils.fromBool, which does exactly what you need here. Or the same thing, less arcane: fromEnum (thanks @bheklilr).

But I think the simplest trick would be to simply avoid counting yourself, and just apply the standard length function after filtering for the number.

1
votes

Using the Enum instance for Bool, it is possible to build a pointfree replacement for if that can be used in more general cases:

chk :: Bool -> (a,a) -> a
chk = ([snd,fst]!!) . fromEnum

Using chk we can define a different version of addIf:

addIf' :: Eq a => a -> a -> Int -> Int
addIf' = curry (flip chk ((+1),id) . uncurry (==))

Now we can simply replace chk in addIf':

addIf :: Eq a => a -> a -> Int -> Int
addIf = curry (flip (([snd,fst]!!) . fromEnum) ((+1),id) . uncurry (==))
0
votes

I think you’re looking for Data.Bool’s bool, which exists since 4.7.0.0 (2014–04–08).

incif :: (Eq a, Enum counter) => a -> a -> counter -> counter
incif = ((bool id succ) .) . (==)

The additional . allows == to take two parameters, before passing the expression to bool.

Since the order of parameters is different, you need to use incif like this:

(flip . incif)

(Integrating that into incif is left as an exercise to the reader. [Translation: It’s not trivial, and I don’t yet know how. ;])

0
votes

Remember that in Haskell list comprehensions, if conditionals can be used in the result clause or at the end. But, most importantly, guards without if can be used to filter results. I am using pairs from zip. The second of the pair is the list number. It stays constant while the elements of the list are being compared to the constant (k). Your result [1,2,0] does not include list numbers 1, 2 or 3 because it is obvious from the positions of the sums in the result list. The result here does not add the occurrences in each list but list them for each list.

nocc k ls = [ z | (y,z) <- zip ls [1..length ls], x <- y, k == x]
nocc 1 [[1, 2], [2, 3, 2, 1, 1], [3]]

[1,2,2] -- read as [1,2,0] or 1 in list 1, 2 in list 2 and 0 in list 3