Разве невозможно получить глубину элементов внутри Traversable? - PullRequest
Новая
       42

Разве невозможно получить глубину элементов внутри Traversable?

3 голосов
/ 26 сентября 2019

Предположим, у меня есть Tree тип: 

{-# LANGUAGE DeriveFoldable, DeriveFunctor #-}

data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving(Functor,Foldable)

instance Traversable Tree where -- equivalent to the one I could derive, but written out for clarity
  traverse _ Leaf = pure Leaf
  traverse f (Branch l x r) = Branch <$> traverse f l <*> f x <*> traverse f r

Легко написать функцию для вычисления максимальной глубины вещей внутри этого конкретного типа: 

depth Leaf = 0
depth (Branch l _ r) = 1 + max (depth l) (depth r)

Но этоНе так просто рассчитать максимальную глубину вещей внутри произвольного Traversable.Я уже знаю, что просто Functor недостаточно для этого, поскольку вы не получаете информации о «положении» вещей внутри них через fmap, и я также уже знаю, что просто Foldable недостаточно дляэто, поскольку foldr и foldMap оба дают столько структуры, сколько имеют списки.Traversable может быть, тем не менее, потому что он более общий, чем Functor и Foldable.

Однако, после некоторых экспериментов, я не думаю, что есть способ сделать это с Traversableили.Вот моя логика до сих пор.Рассмотрим эти два дерева: 

fooTree = Branch (Branch Leaf () Leaf) () (Branch Leaf () Leaf)
barTree = Branch (Branch Leaf () (Branch Leaf () Leaf)) () Leaf

Теперь traverse (\() -> thingy) fooTree равно: 

Branch <$> (Branch <$> pure Leaf <*> thingy <*> pure Leaf) <*> thingy <*> (Branch <$> pure Leaf <*> thingy <*> pure Leaf)

После большого количества использования Применимых законов и некоторого упрощения это становится: 

(\x y z -> Branch (Branch Leaf x Leaf) y (Branch Leaf z Leaf)) <$> thingy <*> thingy <*> thingy

Аналогично, traverse (\() -> thingy) barTree - это: 

Branch <$> (Branch <$> pure Leaf <*> thingy <*> (Branch <$> pure Leaf <*> thingy <*> pure Leaf)) <*> thingy <*> pure Leaf

После большого количества использования Применимых законов и некоторого упрощения это становится: 

(\x y z -> Branch (Branch Leaf x (Branch Leaf y Leaf)) z Leaf) <$> thingy <*> thingy <*> thingy

Сейчас traverse (\() -> thingy) fooTree и traverse (\() -> thingy) barTree похоже, что они имеют одинаковую «форму» (единственное отличие - лямбда в начале, и даже их типы одинаковы), но они пришли с деревьев, которые имеют разную глубину.Это заставляет меня поверить, что невозможно найти глубину в терминах traverse, но я не уверен на 100% в этом, и я не уверен, как объяснить это строго.

Я правчто это невозможно?Если так, то как это можно объяснить строго?Если нет, то как бы вы это реализовали?

1 Ответ

4 голосов
/ 26 сентября 2019

Это действительно невозможно, так как переход от Foldable к Traversable на самом деле не может помочь.Для получения глубины ваших Tree s требуется объединить информацию из обоих поддеревьев в ветке.Что касается ... 

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

..., любое такое слияние может быть достигнуто только через совокупный аппликативный эффект f результата (законный traverse должен сохранять формуструктура t, и каждое значение b получается из отдельного значения a через функцию a -> f b).Однако получение комбинированного эффекта уже возможно через Foldable ... 

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

... и поэтому дополнительная мощность Traversable здесь не имеет значения.

Если просто указание на traverse_ кажется недостаточно резким, вот альтернативный способ представления последнего шага приведенного выше аргумента.Одним из естественных свойств traverse является то, что Bird et al. Называется «естественность» в типе данных.в Понимание идиоматических обходов назад и вперед (подробности см. в разделе 6 этого документа): 

-- r is a natural transformation that preserves toList:
-- toList = toList . r
fmap r . traverse f = traverse f . r

Рассмотрим произвольную toList сохраняющую перестановку деревьев r :: Tree a -> Tree a, а некоторые f такие, что результат traverse f каким-то образом кодирует глубину дерева.Поскольку, как обсуждалось выше, для целей вычисления глубины важен только комбинированный эффект, fmap (const ()) . traverse f будет кодировать глубину так же, как и traverse f.Теперь давайте возьмем свойство натуральности и составим fmap (const ()) с обеих сторон: 

fmap (const ()) . fmap r . traverse f = fmap (const ()) . traverse f . r
-- Or simply:
fmap (const ()) . traverse f = fmap (const ()) . traverse f . r

Поскольку fmap (const ()) . traverse f кодирует глубину, это означает, что r, что бы это ни было, не изменит глубинудерево.Однако это не тот случай, о чем свидетельствует, например, этот контрпример: 

-- Makes a tree with only leaves as left subtrees, preserving traversal order.
-- Assuming a toList that matches your traverse, or the derived one. 
straighten :: Tree a -> Tree a
straighten = foldr dangle Leaf . toList
    where
    dangle x t = Branch Leaf x t
...