Creating a safe version of Haskell 'init' function

user_2618377 0
Viewed 366

I'm working my way through "Real World Haskell," and the assignment is to make safe versions of head, tail, last, and init. I've succeeded on the first three, but the Maybe typeclass is killing me on init.

Here is my code:

-- safeInit
safeInit    ::  [a] ->  Maybe [a]
safeInit []     =   Nothing
safeInit (x:xs) =   if null xs
                    then Just [x]
                    else x : (safeInit xs)

And here are the resultant errors on loading into GHCI (the function starts on line 23 of the original file:

[1 of 1] Compiling Main             ( ch04.exercises.hs, interpreted )

    > ch04.exercises.hs:27:26: error:
    >     • Couldn't match expected type ‘Maybe [a]’ with actual type ‘[a]’
    >     • In the expression: x : (safeInit xs)
    >       In the expression: if null xs then Just [x] else x : (safeInit xs)
    >       In an equation for ‘safeInit’:
    >           safeInit (x : xs) = if null xs then Just [x] else x : (safeInit xs)
    >     • Relevant bindings include
    >         xs :: [a] (bound at ch04.exercises.hs:25:13)
    >         x :: a (bound at ch04.exercises.hs:25:11)
    >         safeInit :: [a] -> Maybe [a] (bound at ch04.exercises.hs:24:1)    | 27 |                     else x : (safeInit xs)    |                
    > ^^^^^^^^^^^^^^^^^
    > 
    > ch04.exercises.hs:27:31: error:
    >     • Couldn't match expected type ‘[a]’ with actual type ‘Maybe [a]’
    >     • In the second argument of ‘(:)’, namely ‘(safeInit xs)’
    >       In the expression: x : (safeInit xs)
    >       In the expression: if null xs then Just [x] else x : (safeInit xs)
    >     • Relevant bindings include
    >         xs :: [a] (bound at ch04.exercises.hs:25:13)
    >         x :: a (bound at ch04.exercises.hs:25:11)
    >         safeInit :: [a] -> Maybe [a] (bound at ch04.exercises.hs:24:1)    | 27 |                     else x : (safeInit xs)    |                
    > ^^^^^^^^^^^ Failed, no modules loaded.

Any way I mark or don't mark either the x or xs on the last two lines with Just, I get different, but very much related, typing errors. What subtlety on using the Maybe type with lists am I missing?

haskell
2 Answers

The main reason why this does not work is because your expression x : safeInit xs will not typecheck. Indeed, safeInit xs is a Maybe [a], but (:) has type (:) :: a -> [a] -> [a], so the types do not match.

There is also a semantical error. If null xs is True, then you should return Just [] instead of Just [x], since then x is the last element in the list.

You can make use of fmap :: Functor f => (a -> b) -> f a -> f b (so for f ~ Maybe, fmap is fmap :: (a -> b) -> Maybe a -> Maybe b), to alter a value that is wrapped in a Just:

safeInit :: [a] -> Maybe [a]
safeInit [] = Nothing
safeInit [_] = Just []
safeInit (x:xs) = fmap (x:) (safeInit xs)

but this will result in a lot of wrapping and unwrapping of values in a Just. It also means that for an infinite list, it will get stuck in an infinite loop. We can simply check if the list contains at least on element, and then perform the init logic as the result of a function we wrap in a Just:

safeInit :: [a] -> Maybe [a]
safeInit [] = Nothing
safeInit (x:xs) = Just (go xs x)
    where go [] _ = []
          go (x2:xs) x = x : go xs x2
user_675790

One interesting problem is how to write safeInit in terms of foldr. Aside from the fun of the puzzle, this allows it to participate in the list fusion optimization in GHC as a "good consumer", which can improve performance in some cases. We start with the first (naive) version in Willem Van Onsem's answer:

safeInit0 :: [a] -> Maybe [a]
safeInit0 [] = Nothing
safeInit0 [_] = Just []
safeInit0 (x:xs) = fmap (x:) (safeInit0 xs)

The first problem with this is that it's not shaped quite like a fold: it has separate cases for [p] and for p:q:rs. A classic trick for patching this up is to pass a Maybe carrying the previous value in the list.

safeInit1 :: [a] -> Maybe [a]
safeInit1 xs0 = go xs0 Nothing
  where
    -- This first case only happens when
    -- the whole list is empty.
    go [] Nothing = Nothing
    go [] (Just x) = Just [x]
    go (x:xs) Nothing = go xs (Just x)
    go (x:xs) (Just prev) = (prev:) <$> go xs (Just x)

The next problem is semantic: it doesn't work right with infinite or partially defined arguments. We want

safeInit [1..] = Just [1..]

but safeInit1 will diverge in this case, because fmap is necessarily strict in its Maybe argument. But it turns out there's a bit of information we can use: fmap will only be applied to a Just value in this case. Exercise: prove that.

We'll take advantage of that by representing Maybe [a] in a weird way as (Bool, [a]), where Nothing is represented as (False, []) and Just xs is represented as (True, xs). Now we can be lazier:

safeInit2 :: [a] -> Maybe [a]
safeInit2 xs = case helper2 xs of
  (False, _) -> Nothing
  (True, xs) -> Just xs

helper2 :: [a] -> (Bool, [a])
helper2 xs0 = go xs0 Nothing
  where
    go [] Nothing = (False, [])
    go [] _ = (True, [])
    go (x:xs) mb = case mb of
      Nothing -> (True, rest)
      Just p -> (True, p:rest)
      where
        rest = snd (go xs (Just x))

Now this has precisely the shape of a fold:

safeInit3 :: [a] -> Maybe [a]
safeInit3 xs = case helper3 xs of
  (False, _) -> Nothing
  (True, xs) -> Just xs

helper3 :: [a] -> (Bool, [a])
helper3 xs0 = foldr go stop x0 Nothing
  where
    stop Nothing = (False, [])
    stop _ = (True, [])
    go x r mb = case mb of
        Nothing -> (True, rest)
        Just p -> (True, p:rest)
      where
        rest = snd (r (Just x))

You might worry that all these intermediate Maybes and pairs will cause performance problems, but in fact GHC is able to optimize them all away, producing something very much like Willem Van Onsem's optimized implementation.

user_14776670
Related