Why doesn't this typecheck?

Question

compress xs@(_:_:_) = (ifte <$> ((==) <$> head <*> head.tail) <$> ((compress.).(:) <$> head <*> tail.tail) <*> ((:) <$> head <*> compress.tail) ) xs

Results in a type error, but I can't see why. It should be equivalent to

compress xs@(_:_:_) = (ifte (((==) <$> head <*> head.tail) xs) (((compress.).(:) <$> head <*> tail.tail) xs) (((:) <$> head <*> compress.tail) xs))

, which doesn't.

note: ifte = (\ x y z -> if x then y else z) , <$> and <*> are from Control.Applicative .

EDIT: The error is:

Couldn't match expected type `[a]' with actual type `[a] -> [a]'
    In the expression:
        (ifte <$> ((==) <$> head <*> head . tail)
     <$>
       ((compress .) . (:) <$> head <*> tail . tail)
   <*>
     ((:) <$> head <*> compress . tail))
      $ xs
    In an equation for `compress':
        compress xs@(_ : _ : _)
          = (ifte <$> ((==) <$> head <*> head . tail)
         <$>
           ((compress .) . (:) <$> head <*> tail . tail)
       <*>
         ((:) <$> head <*> compress . tail))
          $ xs

I encountered this problem trying to write a pointfree solution to problem 8 of the Ninety-Nine Haskell Problems. I was trying to do it by modifying the pointful solution I had written, which was

compress::Eq a => [a]->[a]
compress [] = []
compress (x:[]) = (x:[])
compress (x:y:xs) = ifte ((==) x y) (compress (x:xs)) (x:(compress (y:xs)))

Answer 1

First, indent. Second, consider using some variables.

Even with more sensible formatting, you can see that it's

compress =
  ifte <$> ((==) <$> head <*> head.tail)
       <$> ((compress.).(:) <$> head <*> tail.tail)
       <*> ((:) <$> head <*> compress.tail)

when it should be

compress =
  ifte <$> ((==) <$> head <*> head.tail)
       <*> ((compress.).(:) <$> head <*> tail.tail)
       <*> ((:) <$> head <*> compress.tail)

Third, even if you must be inscrutable, how about

compress (x:r@(y:_)) = ifte (x==y) id (x:) $ compress r

or, point free

compress = map fst . filter (uncurry (/=)) . (zip <$> id <*> tail)

Answer 2

Here's your code written in a little more readable way

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative

u = ((==) <$> head <*> head.tail)
v = ((compress.).(:) <$> head <*> tail.tail)
w = ((:) <$> head <*> compress.tail)

ifte = (\ x y z -> if x then y else z) 

--compress xs@(_:_:_) = (ifte <$> u <$> v <*> w) xs
compress xs@(_:_:_) = (ifte (u xs) (v xs) (w xs))

I hope you see now the mistake - correct version is

--compress xs@(_:_:_) = (ifte <$> u <*> v <*> w) xs

Answer 3

This is very similar to what has already been said, but indulge me for a moment, and allow me to preach to you the value of types.

import Control.Applicative

ifte :: Bool -> a -> a -> a
ifte b t f = if b then t else f

compress :: Eq a => [a] -> [a]
-- compress = ifte <$> cond <$> t <*> f
-- We will leave compress undefined so we can load this into ghci.
-- After some trial and error it is clear that this is the part
-- that doesn't type check
compress = undefined

cond :: Eq a => [a] -> Bool
cond = (==) <$> head <*> head . tail

t :: Eq a => [a] -> [a]
t = (compress .) . (:) <$> head <*> tail . tail

f :: Eq a => [a] -> [a]
f = (:) <$> head <*> compress . tail

Here I've split it out, and as Brandon mentioned, at this point you should see that the error lies in using <$> where <*> should be. You will get comfortable with that concept as you keep learning applicative style, where your expressions typically have a single <$> followed an arbitrary # of <*>:

f <$> a <*> b <*> c <*> d <*> ...

Ignoring that insight, though, I've given each subexpression here a type and a TLD, temporarily. This lets me load the file into ghci and play around a bit.

ghci> :t ifte <$> cond <$> t <*> f
... Eq a => [a] -> [a] -> [a]

WTF??? It is type sound??? It was supposed to give an error, but apparently this expression is a-OK. Or is it? Notice this type signature doesn't match the one we want for compress.

ghci> :t compress
... Eq a => [a] -> [a]

The sub-expressions match the type signatures that we expect them to, as evidenced by the compiler not vomiting on us. Since that is the case, the problem is clearly in the way we combine them. So what are the pieces we want to combine here? Ignoring the Eq constraints:

ifte :: Bool -> [a] -> [a] -> [a]
cond :: [a] -> Bool
t    :: [a] -> [a]
f    :: [a] -> [a]

-- desired result
     :: [a] -> [a]

Here I've made the trivial specialization of ifte for [a] instead of any a. The relationship is clear: the output type of cond, t, and f match the input types of ifte. We just need to feed all three of those expressions the same [a]. Recognizing that (input ->) is applicative, we generalize:

arg1 :: (a -> b -> c -> d)
arg2 :: f a
arg3 :: f b
arg4 :: f c
res  :: f d

-- for our case,
-- f = ([a] ->)
-- a = Bool
-- b = [a]
-- c = [a]
-- d = [a]

Stop...Hoogle time! Hoogling (a -> b -> c -> d) -> f a -> f b -> f c -> f d, we immediately find liftA3, which is, not surprisingly defined:

liftA3 f a b c = f <$> a <*> b <*> c