Отличается ли Traversable для деревьев шириной и глубиной? - PullRequest
Новая
       38

Отличается ли Traversable для деревьев шириной и глубиной?

2 голосов
/ 10 июня 2019

У меня есть структура Rose Tree, и я хотел написать для нее экземпляр Traversable.Поэтому я начал со следующего: 

data Tree a = Tree a [Tree a] deriving (Show)

instance Functor Tree where
  fmap f (Tree x subs) = Tree (f x) (fmap (fmap f) subs)

Я сделал первый вариант глубины: 

newtype Depth a = Depth (Tree a) deriving (Show)

depth :: Tree a -> [a]
depth (Tree x subs) = x : concatMap depth subs

instance Functor Depth where
  fmap f (Depth t) = Depth $ fmap f t

instance Foldable Depth where
  foldMap f (Depth t) = mconcat $ f <$> depth t

instance Traversable Depth where
  traverse f (Depth t) = Depth <$> go t
    where go (Tree x subs) = Tree <$> f x <*> traverse go subs

Затем я попробовал вариант в ширину: 

newtype Breadth a = Breadth (Tree a) deriving (Show)

breadth :: Tree a -> [a]
breadth tree = go [tree]
  where
    go [] = []
    go (Tree x subs:q) = x : go (q <> subs)

instance Functor Breadth where
  fmap f (Breadth t) = Breadth $ fmap f t

instance Foldable Breadth where
  foldMap f (Breadth t) = mconcat $ f <$> breadth t

instance Traversable Breadth where
  traverse f (Breadth t) = ???

И я понял, что ширина и глубина первых вариантов Traversable для этого должны быть одинаковыми.Это тот случай?Я не думаю, что на самом деле читал это где-нибудь, но обход не зависит от порядка элементов?

Если это так, это становится немного странным, потому что Traversable может быть реализован непосредственно для Tree, что означает, что Foldable должен быть реализован для Tree, но очевидно, что Foldable может быть реализовано несколькими способами.

1 Ответ

5 голосов
/ 10 июня 2019

Traversable должен согласиться с Foldable.В частности, если Monoid m, то Applicative (Const m), что вызывает закон согласованности foldMap f = getConst . traverse (Const . f).Таким образом, невозможно для Breadth и Depth для совместного использования Traversable.Существует либо другая реализация для Traversable Breadth, которая согласуется с Foldable, либо ее вообще нет.Я могу подготовить реализацию, которая, на мой взгляд, согласуется, но я не проверил другие законы. 

instance Traversable Breadth where
  traverse f (Breadth t) = Breadth <$> head <$> go [t]
    where
      go [] = pure []
      go ts = zipWith Tree <$> traverse f rs
                           <*> (fmap (rebuild css) $ go $ concat css)
        where
          (rs, css) = unzip $ map (\(Tree r cs) -> (r, cs)) ts
          -- rebuild s d = evalState (traverse (state splitAt') d) s
          -- I think, but let's keep the dependencies down, shall we?
          rebuild [] [] = []
          rebuild (struct : structs) destruct
            = let (cs, destruct') = splitAt' struct destruct
              in  cs : rebuild structs destruct'
          -- ignoring the as in a [a] makes it look like a number
          splitAt' [] xs = ([], xs)
          splitAt' (_ : n) (x : xs)
            = let (pre, suf) = splitAt' n xs
              in  (x : pre, suf)

Это довольно странно, и повсюду есть не совокупность, но она должна работать нормально.

...