Поднятие (Объектив) Обхода, чтобы Исправить - PullRequest
Новая
       10

Поднятие (Объектив) Обхода, чтобы Исправить

0 голосов
/ 04 января 2019

У меня есть следующий код.Как вы можете видеть, последняя функция undefined. 

{-# LANGUAGE TemplateHaskell, DeriveFunctor, DeriveTraversable #-}

module Example where

import Control.Lens
import Data.Functor.Foldable

data PathComponent d a = Directions d | Alt [a] deriving (Show, Functor, Foldable, Traversable)

makePrisms ''PathComponent

newtype Path d a = Path [PathComponent d a] deriving (Show, Functor, Foldable, Traversable)

directions :: Traversal (Path a p) (Path b p) a b
directions a2fb (Path l) = Path <$> traverse f l where
    f (Directions d) = Directions <$> a2fb d
    f (Alt p) = (pure . Alt) p

directions' :: Traversal (Fix (Path a)) (Fix (Path b)) a b
directions' = undefined

В конечном итоге я хочу сделать рекурсивное сопоставление каждого a с b в структуре.Я надеялся, что смогу сделать это, подняв directions, но, похоже, меня сдерживает а) тот факт, что функция объявляет p в позициях s и t, а также б) тот факт, что _WrappingIso' не Iso.Есть ли элегантный способ исправить это?

1 Ответ

0 голосов
/ 04 января 2019

В directions нам нужно пересечь p с a2fb тоже.Поскольку p является параметром, мы можем принять его обход в качестве параметра.Кроме того, f, который вы определили, на самом деле является обходом PathComponent, который мы также можем извлечь.

Во-первых, обход PathComponent a p, который параметризуется обходомp (и обобщенно, поэтому типы источника и цели могут различаться): 

data PathComponent d a = Directions d | Alt [a] deriving (Show, Functor, Foldable, Traversable)

{- Morally

traversePC ::
  Traversal pa pb a b ->
  Traversal (PathComponent a pa) (PathComponent b pb) a b

   But the following type is both simpler (rank 1) and more general.
-}
traversePC ::
  Applicative m =>
  LensLike m pa pb a b ->
  LensLike m (PathComponent a pa) (PathComponent b pb) a b
traversePC _tp f (Directions d) = Directions <$> f d
traversePC  tp f (Alt pas) = Alt <$> (traverse . tp) f pas

В случае Directions мы преобразуем a в b напрямую.В случае Alt у нас есть список pa, поэтому мы составляем обход этого списка (traverse) с обходом параметра (tp).

Обход Path передает tp в traversePC. 

newtype Path d a = Path [PathComponent d a] deriving (Show, Functor, Foldable, Traversable)

{- Same idea about the types.

directions :: Traversal pa pb a b -> Traversal (Path a pa) (Path b pb) a b

-}

directions ::
  Applicative m =>
  LensLike m pa pb a b ->
  LensLike m (Path a pa) (Path b pb) a b
directions tp f (Path l) = Path <$> (traverse . traversePC tp) f l

И, наконец, для прохождения Fix (Path a), это распаковывается в h :: Path a (Fix (Path a)), и мы передаем обход уровня верхнего уровня для Fix (Path a) рекурсивно. 

directions' :: Traversal (Fix (Path a)) (Fix (Path b)) a b
directions' f (Fix h) = Fix <$> directions directions' f h

На самом деле, здесь есть общая схема для любого Fix.Если у вас есть функтор f (здесь Path a), и есть обход f x, параметризованный обходом x, то вы можете связать узел, чтобы получить обход traverseFix' из Fix f, применяя параметризованный обход к самому traverseFix'. 

{-

traverseFix ::
  (forall x y. Traversal x y a b -> Traversal (f x) (g y) a b) ->
  Traversal (Fix f) (Fix g) a b

-}

traverseFix ::
  Functor m =>
  (forall x y. LensLike m x y a b -> LensLike m (f x) (g y) a b) ->
  LensLike m (Fix f) (Fix g) a b
traverseFix traverseF = traverseFix' where
  traverseFix' f (Fix h) = Fix <$> traverseF traverseFix' f h

Таким образом, мы можем переопределить directions' следующим образом: 

directions'' :: Traversal (Fix (Path a)) (Fix (Path b)) a b
directions'' = traverseFix directions

Полный смысл

...