Haskel - Implementation of <*> of List

Question

I'd like to implement my list in Haskell. But I can't do this. The implementation of <*> causes

data List a = a :+ (List a) | Empty deriving Show
infixr 9 :+

instance Functor List where
  fmap _ Empty     = Empty
  fmap f (a :+ xs) = f a :+ fmap f xs

instance Applicative List where
  pure x           = x :+ Empty
  Empty     <*> _  = Empty
  (f :+ fs) <*> xs =  fmap f xs :+  (fs <*> xs) -- Error

main :: IO ()
main = do
  print $ 1 :+ 2 :+ 3 :+ Empty
  print $ fmap (^2) (1 :+ 2 :+ 3 :+ Empty)
  print $ ((+1) :+ (*2) :+ (^2) :+ Empty) <*> (1 :+ 2 :+ 3 :+ Empty)

The error is

Couldn't match expected type ‘b’ with actual type ‘List b’ ‘b’ is a rigid type variable bound by ...

You're trying to use :+ constructor to concatenate two lists. — zaquest

Random Dev Random Dev · Accepted Answer · 2016-06-01T13:38:29

as zaquest pointed out you are prepending instead of concatenating.

So first implement a concat:

infixr 5 +:+
(+:+) :: List a -> List a -> List a
Empty +:+ ys = ys
(x :+ xs) +:+ ys = x :+ (xs +:+ ys)

and then use it instead in

(f :+ fs) <*> xs =  fmap f xs +:+  (fs <*> xs)

(PS: of course you can rename it - I thought +:+ looked moste like :+ here)

Haskel - Implementation of <*> of List

1 Answers