CODEWITHSUNDEEP
haskell
Peter
Peter

Reputation: 3135

haskell initial accumulator 'null' value

I have a seemingly simple Haskell problem and with my limited knowledge I'm not sure what terms to search for in order to solve it.

I've tried to solve problem number 8 from the 99 Haskell problems (removing consecutive duplicates from a list) and this is what I've come up with:

compress :: (Eq a) => [a] -> [a]
compress list = compress' list ???
  where
    compress' [] _ = []
    compress' (x:xs) last
      | x == last = compress xs last
      | otherwise = x : compress xs x

'???' is just a placeholder, this is where I'm unsure what to do. I suppose how the snippet is intended to work should be clear enough, 'last' is an accumulator of sorts which is used to check whether elements are duplicates of previous ones. Now, what initial value can I give 'last' in this case? (something akin to 'null' in most OO languages I suppose).

edit: Tikhon's answer works, however I just realized that I have made a mistake in my original post, compress' should recursively call itself and not compress. Thus the 'trivial' solution to my problem is now:

compress :: (Eq a) => [a] -> [a]
compress list = compress' list Nothing
  where
    compress' [] _ = []
    compress' (x:xs) Nothing = x : compress' xs (Just x)
    compress' (x:xs) (Just last)
      | x == last = compress' xs (Just last)
      | otherwise = x : compress' xs (Just x)

Upvotes: 2

Views: 142

Answers (1)

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

So there are two answers to your question. The more literal answer is that you can use Maybe to make something nullable, and the type system will make sure you check whether something is Nothing each time you use it:

compress list = compress' list Nothing
  where compress' [] _ = []
        compress' (x:xs) Nothing = x : compress xs (Just x)
        compress' (x:xs) (Just last)
          | x == last = compress xs last
          | otherwise = x : compress xs (Just x)

The moral of the story is that if you have an element which might be missing (ie could be null in other languages), you wrap it in Maybe. Then you either have Just x or Nothing, and you can pattern match on it the same way you pattern match on a list.

However, in this particular case, we can have a cleaner solution. Note that the element is only missing the first time you call compress'. We can deal with this by adding a case to the top-level compress function which handles this possibility:

compress [] = []
compress (x:xs) = x : compress' xs x
  where ...

Essentially, we can avoid needing to handle the case in our helper compress' function if we instead handle it in the top-level function, where we can match on the list passed in to decided what to do.

Upvotes: 9

Related Questions