В книге Haskell «Программирование на Haskell из первых принципов» есть упражнение, в котором мне предлагается создать экземпляр Applicative
с типом данных List
:
data List a =
Nil
| Cons a (List a)
deriving (Eq, Show)
instance Functor List where
fmap _ Nil = Nil
fmap f (Cons x xs) = Cons (f x) (fmap f xs)
instance Applicative List where
pure x = Cons x Nil
Nil <*> _ = Nil
_ <*> Nil = Nil
Cons f fs <*> Cons x xs = Cons (f x) ((fmap f xs) <> (fs <*> xs))
Я написал приведенный выше код и обнаружил, что сначала должен установить Semigroup
, чтобы оператор <>
работал.
Можно ли это сначала реализовать без экземпляра Semigroup
?
да. Здесь вы используете функцию (<>)
в своем определении:
instance Applicative List where
pure x = Cons x Nil
Nil <*> _ = Nil
_ <*> Nil = Nil
Cons f fs <*> Cons x xs = Cons (f x) ((fmap f xs) <> (fs <*> xs))
-- ^ call to the (<>) function
так что вы можете заменить это вызовом другой функции:
instance Applicative List where
pure x = Cons x Nil
Nil <*> _ = Nil
_ <*> Nil = Nil
Cons f fs <*> Cons x xs = Cons (f x) (append (fmap f xs) (fs <*> xs))
where append = ...
Однако обратите внимание, что здесь вы, вероятно, реализуете другую функцию, чем та, которую вы намереваетесь здесь. Здесь вы реализовали функцию, которая для двух списков [f1, f2, f3]
и [x1, x2, x3, x4]
будет вычислять список с «верхним треугольником» матрицы fs
и xs
, так что это приведет к [f1 x1, f1 x2, f1 x3, f1 x4, f2 x2, f2 x3, f2 x4, f3 x3, f3 x4]
. Обратите внимание, что здесь отсутствуют f2 x1
, f3 x1
и f3 x2
.
Хорошо, вы используете что-то под названием <>
, и Haskell знает, что эта вещь (в частности, определение <>
, которое вы импортировали, поскольку вы нигде не определили оператор), требует полугруппы. Решение состоит в том, чтобы использовать другое имя или определить его локально:
Cons f fs <*> xs = (f <$> xs) <> (fs <*> xs)
where xs <> Nil = xs
Nil <> xs = xs
Cons x xs <> ys = Cons x (xs <> ys)
Конечно, просто укажите именованную функцию конкатенации для вашего типа
List
и используйте ее вместо<>
. Но почему?