Haskel - リストの<*>の実装

Question

私はHaskellで私のリストを実装したいと思います。 しかし、私はこれを行うことはできません。 <*>の実装は

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) 

の原因となるエラーが

である「B」 実際の型「リストB」で期待される型「B」と一致しませんでした

...に縛ら剛性型変数であります

Answer 1

zaquestが指摘しているように、連結する代わりにプリペンドしています。

だから、最初の連結を実装：

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

、その後

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

で代わりにそれを使用します（PS：もちろんあなたはそれを名前を変更することができます - 私は+:+がここ:+ようMOSTEに見えたと思った）