Борьба с реализацией функции Монады - PullRequest
Новая
       9

Борьба с реализацией функции Монады

0 голосов
/ 22 ноября 2018

Недавно я играю с монадой Haskell и пытаюсь узнать об этой концепции.

Допустим, объявлен тип данных дерева, который может иметь несколько поддеревьев. 

data MyTree a = MyTree a [MyTree a]

И я пытаюсь реализовать функцию, которая возвращает «Nothing», если дерево содержит какое-либо значение «Nothing» в дереве.Иначе, извлеките все значения m и верните упакованное дерево.

Таким образом, сигнатура типа функции имеет следующее. 

check :: Monad m => MyTree (m a) -> m (MyTree a)

А вот моя текущая реализация. 

check (MyTree v []) = v >>= (\v' -> return (MyTree v' []))
check (MyTree v (x:xs)) =
  v >>= (\v' -> check x >>= (\t' -> return (MyTree v' [t'])))

Я использую оператор связывания для v, чтобы получить его чистое значение.Затем я вызываю функцию "check" рекурсивно со значением head из списка.Наконец, я обертываю окончательные результаты.

Я протестировал с некоторыми образцами и получил следующие результаты. 

> test1 = MyTree (Just 1) [MyTree (Just 2) [MyTree (Just 3) []]]
> check test1
Just (MyTree 1 [MyTree 2 [MyTree 3 []]])

> test2 = MyTree (Just 1) [MyTree (Just 2) [], MyTree (Just 3) []]
> check test2
-- expected: Just (MyTree 1 [MyTree 2 [], MyTree 3 []]
-- actual:   Just (MyTree 1 [MyTree 2 []])

Итак, текущая реализация имеет проблему, когда входное дерево имеет несколько вложенных элементов.деревья.И я понял, что проблема в том, что я использую только x, а не xs.Я обернул голову, чтобы подумать о правильном подходе и все еще выяснять.Будет очень полезно, если у кого-то есть идея для этого.

1 Ответ

0 голосов
/ 22 ноября 2018

Ваша функция check более известна как метод класса Traversable. 

class (Functor t, Foldable t) => Traversable t where
  -- The main method
  traverse
    :: Applicative f
    => (a -> f b) -> t a -> f (t b)
  traverse f = sequenceA . fmap f

  -- An alternative
  sequenceA
    :: Applicative f
    => t (f a) -> f (t a)
  sequenceA = traverse id

  -- (Mostly) legacy methods
  mapM
    :: Monad m
    => (a -> m b) -> t a -> m (t b)
  mapM = traverse

  sequence
    :: Monad m
    => t (m a) -> m (t a)
  sequence = sequenceA

В частности, check - это sequence для MyTree.Таким образом, мы получим его, если напишем экземпляр Traversable MyTree.Но давайте сначала сделаем шаг назад в двух направлениях.Traversable является подклассом Functor и Foldable, и это не случайно.Можно реализовать как fmap, так и foldMap, используя traverse.Но, что более важно, структуры fmap, foldMap и traverse имеют тенденцию выглядеть почти одинаково!Итак, начнем с более простых. 

instance Functor MyTree where
  fmap f (MyTree a ts) = MyTree (f a) _

Что входит в этот пробел?У нас есть список поддеревьев, и нам нужно сгенерировать новое, поэтому хорошей ставкой будет 

  fmap f (MyTree a ts) = MyTree (f a) (fmap _ ts)

Теперь бланк имеет тип MyTree a -> MyTree b, поэтому мы просто вызываем fmap рекурсивно: 

  fmap f (MyTree a ts) = MyTree (f a) (fmap (fmap f) ts)

И мы закончили.Теперь давайте обратимся к Foldable. 

foldMap f (MyTree a ts) = _

Что ж, нам нужно применить f к a, чтобы получить значение в моноиде, затем сложить поддеревья и объединитьРезультаты.В итоге это выглядит как fmap, как и было обещано. 

foldMap f (MyTree a ts) = f a <> foldMap (foldMap f) ts

Так что теперь мы получаем Traversable.Это будет очень похоже на fmap, но нам нужно объединить результаты, используя Applicative операции несколько , как мы объединяли foldMap результаты, используя Monoid операции. 

instance Traversable MyTree where
   traverse f (MyTree a ts) = _

У нас есть 

a :: a
ts :: [MyTree a]
f :: a -> f b

Очевидно, мы хотим применить f к a.Следуя схеме для fmap и foldMap, мы собираемся вычислить traverse (traverse f) ts.Итак, давайте посмотрим, куда это нас приведет: 

traverse f (MyTree a ts) = _ (f a) (traverse (traverse f) ts)

Теперь GHC скажет нам, что 

_ :: f b -> f [MyTree b] -> f (MyTree b)

Нам нужно взять b результат первого действия и [MyTree b]результат второго действия и примените конструктор MyTree, чтобы собрать их вместе.Мы можем сделать это, используя liftA2: 

traverse f (MyTree a ts) = liftA2 MyTree (f a) (traverse (traverse f) ts)

После того, как вы освоите написание экземпляров Functor, Foldable и Traversable, это будет довольно красиво.тупой.Так что у GHC есть расширение, которое позволяет компилятору написать их для вас. 

{-# language DeriveTraversable #-}

module MyModule where

data MyTree a = MyTree a [MyTree a]
  deriving (Functor, Foldable, Traversable)

И все готово.

...