Search code examples
haskelltypesfoldunfold

Weird couldn't match type error


I have simple one line function:

revRange :: (Char,Char) -> [Char]
revRange t = unfoldr (\b -> if b == (pred (fst t)) then Nothing else Just (b, pred b)) (snd t)

It works well:

*Main Data.List> revRange ('a', 'f')
"fedcba"

Then I want to extract unfoldr lambda as unique function:

revRange :: (Char,Char) -> [Char]
revRange t = unfoldr fun t
fun t = (\b -> if b == (pred (fst t)) then Nothing else Just (b, pred b)) (snd t)

Now, I have a weird error:

Couldn't match type `Char' with `(Char, Char)'
Expected type: (Char, Char) -> Maybe (Char, (Char, Char))
  Actual type: (Char, Char) -> Maybe (Char, Char)
In the first argument of `unfoldr', namely `fun'
In the expression: unfoldr fun t

Solution

  • First, format your code:

    revRange :: (Char,Char) -> [Char]
    revRange t = unfoldr fun t
    fun t = (\b -> if b == (pred (fst t)) 
                   then Nothing 
                   else Just (b, pred b)) (snd t)
    

    Next, double check the type of unfoldr using Hoogle:

    unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
    

    Next, add a type signature to fun so that GHC will tell you what the problem is. According to the type of unfoldr, fun should have the type:

    b ~ Char
    a ~ Char
    
    fun :: Char -> Maybe (Char, Char)
    

    since you are unfoldr in the original example with snd t.

    I usually like to verify small pieces, so we can remove the definition of foo and just use the type signature:

    revRange :: (Char,Char) -> [Char]
    revRange t = unfoldr fun t
    
    fun:: Char -> Maybe (Char, Char)
    fun b = error ""
    

    GHC complains that t has type (Char, Char) but fun expects type Char. You've called unfoldr fun t instead of unfoldr fun (snd t) as in the original example. Move that bit from fun into revRange:

    revRange :: (Char,Char) -> [Char]
    revRange t = unfoldr fun (snd t)
    
    fun:: Char -> Maybe (Char, Char)
    fun b = error ""
    

    Next, add in the definition of fun again. We can remove the lambda and put b as a normal argument to fun:

    fun:: Char -> Maybe (Char, Char)
    fun t b = if b == (pred (fst t)) 
              then Nothing 
              else Just (b, pred b)
    

    Immediately we see another glaring problems: fun takes two arguments but the signature says it should only take one!

    Since t is a constant in the original lambda, we can solve this problem by partially applying fun in revRange, so the final answer is:

    revRange :: (Char,Char) -> [Char]
    revRange t = unfoldr (fun t) (snd t)
    
    fun:: (Char, Char) -> Char -> Maybe (Char, Char)
    fun t b = if b == (pred (fst t)) 
              then Nothing 
              else Just (b, pred b)
    

    To address your comment, you'd like to write

    revRange :: (Char,Char) -> [Char]
    revRange = unfoldr fun2
    

    Using the same approach as above, in the signature of unfoldr we need b ~ (Char,Char) and a ~ Char. So we'd like fun2 to have the type

    fun2 :: ((Char,Char) -> Maybe (Char, (Char, Char)))
    

    I'll leave the definition of fun2 as an exercise. As a hint, I suggest adopting the convention that the first part of the pair is constant and holds fst t.