Реализация Applicative для пользовательских ZipList - PullRequest
Новая
       55

Реализация Applicative для пользовательских ZipList

3 голосов
/ 28 октября 2019

Это происходит из упражнения в книге Haskell из Первых принципов . Упражнение заключается в реализации Applicative для ZipList', что аналогично прелюдии ZipList. В этой книге есть подсказка

Проверьте Prelude для функций, которые могут дать вам то, что вам нужно. Один начинается с буквы z, другой - с буквы r. Вы ищете вдохновение от этих функций, а не для возможности их непосредственного повторного использования, поскольку вы используете пользовательский тип List, а не предоставленный тип списка Prelude.

Я догадалсяфункция, которая начинается с z - это zipWith, но я не знаю, какая функция начинается с r. 

data List a =
    Nil
  | Cons a (List a)
  deriving (Eq, Show)

zipWith' :: (a -> b -> c) -> List a -> List b -> List c
zipWith' _ Nil _ = Nil
zipWith' _ _ Nil = Nil
zipWith' f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith' f xs ys)

newtype ZipList' a = ZipList' (List a)
  deriving (Eq, Show)

instance Functor ZipList' where
  fmap f (ZipList' xs) = ZipList' $ fmap f xs

instance Applicative ZipList' where
  pure x = ZipList' $ Cons x Nil
  (ZipList' fs) <*> (ZipList' xs) = ZipList' $ zipWith' ($) fs xs

. В книге проходит тестовый пример, но мне интересноесли есть лучший способ реализовать это, так как я не использовал функцию, которая начинается с r. У меня такое ощущение, что это должно было быть repeat, потому что оно также должно работать над бесконечными списками.

Ответы [ 2 ]

3 голосов
/ 28 октября 2019

Читая ветку под оригинальным постом, я пришел к выводу, что автор поста пытается доказать, что реализация удовлетворяет закону (fmap f xs = (pure f) <*> xs):

Давайте попробуем доказать это как классическийличность, избавляясь от обертки. Итак, давайте поработаем с правой рукой:

(pure f) <*> xs = (repeat' f) <*> xs = zipWith' ($) (repeat' f) xs;

Что касается идентичности, достаточно доказать, что zipWith' ($) (repeat' f) xs равно fmap f xs.

Причина, по которой они одинаковые, довольно очевидна:

length (zipWith op xs ys) == min (length xs) (length ys);(это выражение не может быть оценено в случае, когда xs и ys бесконечны).

Поскольку repeat' f бесконечно, length $ zipWith' ($) (repeat' f) xs фактически является length xs (здесь онона самом деле не имеет значения, существует ли такая величина: было бы достаточно наличия индексов). Каждый элемент xs применяется к той же функции f, которая повторяется. Как видите, размер сохраняется, и каждый элемент трансформируется в постоянную функцию, которая является определением fmap.

2 голосов
/ 28 октября 2019

Я немного подумал об этом после комментария Робина Зигмонда :

Ключ к размышлению о требовании законного Applicative экземпляра, который fmap f x == (pure f) <*> x,и признать, что нет верхнего предела длины списка x.

Эта реализация должна удовлетворять Применимому законодательству. 

data List a =
    Nil
  | Cons a (List a)
  deriving (Eq, Show)

zipWith' :: (a -> b -> c) -> List a -> List b -> List c
zipWith' _ Nil _ = Nil
zipWith' _ _ Nil = Nil
zipWith' f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith' f xs ys)

repeat' :: a -> List a
repeat' x = Cons x $ repeat' x

newtype ZipList' a = ZipList' (List a)
  deriving (Eq, Show)

instance Functor ZipList' where
  fmap f (ZipList' xs) = ZipList' $ fmap f xs

instance Applicative ZipList' where
  pure x = ZipList' $ repeat' x
  (ZipList' fs) <*> (ZipList' xs) = ZipList' $ zipWith' ($) fs xs
...