CODEWITHSUNDEEP
listhaskellfunctional-programmingoption-type
Anonnnn
Anonnnn

Reputation: 53

Cut out Nothing with foldl

I have a list [Maybe a] where I want to cut out the Nothing elements with a function that uses foldl For example cut [Just 2, Just 10, Nothing, Just 5] -> [2,10,5]

I wrote:
cut :: [Maybe a] -> [a]
cut a = foldl (help) [] a
               where help (x:xs) Nothing = (x:xs)
                     help (x:xs) Just a = a:(x:xs)

Where is my mistake?

Upvotes: 2

Views: 221

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476719

By writing help (x:xs) Nothing = (x:xs) you have used a pattern (x:xs) this means that you expect the accumulator to be a list with at least one element. But that is not always the case, for instance the initial accumulator [] is the empty list.

We can simply use a variable l, instead of a pattern:

cut :: [Maybe a] -> [a]
cut a = foldl help [] a
               where help l Nothing = l
                     help l (Just a) = a:l

Note that you also need to add brackets for a constructor with arguments.

But this will not solve the entire pattern, now you will have reversed the list. This is because foldl iterates through the list left-to-right, so you prepend values while you iterate through the list. We can use foldr instead. But now the type of the function does no longer works, since the help function in foldr takes the accumulator as second argument. So we can flip the arguments:

cut :: [Maybe a] -> [a]
cut a = foldr help [] a
               where help Nothing l = l
                     help (Just a) l = a:l

And now it works. We can however clean up the code a bit. For instance use an eta-reduction on the cut function: we can remove a in the head and body of the function:

cut :: [Maybe a] -> [a]
cut = foldr help []
               where help Nothing l = l
                     help (Just a) l = a:l

and since the second argument in help can be removed and the body converted into functions:

cut :: [Maybe a] -> [a]
cut = foldr help []
               where help Nothing = id
                     help (Just a) = (a:)

We can also use another catamorphism: foldr is the catamorphism of a list, and maybe is the catamorphism of Maybe, so we can write a:

maybe <value-in-case-of-nothing> <function-just-value> <Maybe value>

So we can rewrite our help to:

import Data.Maybe(maybe)

cut :: [Maybe a] -> [a]
cut = foldr help []
               where help = maybe id (:)

or simply inject it as an argument of foldr:

import Data.Maybe(maybe)

cut :: [Maybe a] -> [a]
cut = foldr (maybe id (:)) []

So now we used a catamporhism inside a catamorphism, so catamorphception.

Upvotes: 3

Related Questions