對于不可折疊的東西，是否有地圖累積？

假設我有一棵二叉樹：

data BinTree a
  = Nil
  | Branch a (BinTree a) (BinTree a)

我想在這樣的結構上做一個累積映射：

mapAccum ::
  (
  )
    => (a -> b -> (c, a)) -> a -> BinTree b -> BinTree c
mapAccum func x Nil =
  Nil
mapAccum func x (Branch y left right) =
  let
    (y', x') =
      func x y
  in
    Branch y' (mapAccum func x' left) (mapAccum func x' right) 

它使用跨結構的累加器執行映射。

然而，這是一個非常普遍的模式。我們可以在各種樹狀結構上執行此操作，如果有一個不錯的、通用的抽象，我更愿意使用它而不是在這里滾動我自己的。

Traversables上有一個函式：

mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

哪種在串列上做同樣的事情。但它需要Foldable的方式意味著它不適用于二叉樹。我正在尋找的是一個更基本的版本，它不需要Foldable.

我可以讓它在用Cofree以下方法制作的型別上作業：

mapAccum ::
  ( Functor f
  )
    => (a -> b -> (c, a)) -> a -> Cofree f b -> Cofree f c
mapAccum func x (y :< rest) =
  let
    (y', x') =
      func x y
  in
    y' :< fmap (mapAccum func x') rest

這表明它至少普遍適用于樹狀結構。

這個函式有共同的抽象嗎？

uj5u.com熱心網友回復：

這是您使用bifunctors和recursion-schemes包撰寫的內容的概括：

{-# LANGUAGE TemplateHaskell, TypeFamilies #-}

import Control.Monad.Trans.State.Lazy
import Data.Bifunctor.TH
import Data.Bitraversable
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

data BinTree a = Nil | Branch a (BinTree a) (BinTree a)
makeBaseFunctor ''BinTree
deriveBifunctor ''BinTreeF
deriveBifoldable ''BinTreeF
deriveBitraversable ''BinTreeF

mapAccum :: (Base tc ~ f c, Base tb ~ f b, Bitraversable f, Recursive tb,
  Corecursive tc) => (a -> b -> (c, a)) -> a -> tb -> tc
mapAccum func x ys = embed ys' where
  (ys', x') = runState (bitraverse (state . flip func) (pure . mapAccum func x') (project ys)) x

-- a slightly less general version, but that's usually good enough,
-- and will fix most ambiguous type errors
mapAccum' :: (Base (t c) ~ f c, Base (t b) ~ f b, Bitraversable f, Recursive (t b),
  Corecursive (t c)) => (a -> b -> (c, a)) -> a -> t b -> t c
mapAccum' = mapAccum

它的作業方式是遍歷樹的當前元素中的所有值（特別是對于您的樹，這始終只是一個元素），轉換它們并得出一個新的累加器值，然后遞回呼叫自身在具有該值的樹的每個子元素上。此外，由于它是惰性狀態，它打結，所以它只需要走一次結構而不是兩次。換句話說，請注意x'來自 的輸出runState，但它作為引數的一部分傳遞給它。在嚴格的語言中，這將導致無限回圈，但由于 Haskell 是惰性的，x'因此在需要之前不會對其進行評估，此時生成它的代碼部分已完成。

uj5u.com熱心網友回復：

import Data.Functor.Foldable.TH
import Data.Functor.Foldable

data BinTree a
  = Nil
  | Branch a (BinTree a) (BinTree a)
  deriving (Functor)

makeBaseFunctor ''BinTree

模板 Haskell 拼接將定義

data BinTreeF a x
  = NilF
  | BranchF a x x
  deriving (Functor)

還有的情況下，Base家庭型別與Recursive和Corecursive上課BinTree。多虧了那個Recursive實體，你可以使用

cata :: Recursive t => (Base t r -> r) -> t -> r

在型別

cata :: (BinTreeF b (BinTree c) -> BinTree c) -> BinTree b -> BinTree c

具體來說，

mapAccum:: a -> b -> (c, a)) -> a -> BinTree b -> BinTree c
mapAccum func = \x t -> cata go t x
  where
    go NilF _x = Nil
    go (BranchF y leftres rightres) x =
      let
        (y', x') = func x y
      in
        Branch y' (leftres x') (rightres x') 

或者，您可以使用

transverse :: (Recursive s, Corecursive t, Functor f) 
           => (forall r. Base s (f r) -> f (Base t r)) 
           -> s -> f t

在型別

transverse :: (forall r. BinTreeF b (a -> r) -> a -> BinTreeF c r) 
           -> BinTree b -> a -> BinTree c

像這樣

mapAccum:: forall a b c. (a -> b -> (c, a)) -> a -> BinTree b -> BinTree c
mapAccum func = \x t -> transverse go t x
  where
    go :: BinTreeF b (a -> r) -> a -> BinTreeF c r
    go NilF _x = NilF
    go (BranchF y leftres rightres) x =
      let
        (y', x') = func x y
      in
        BranchF y' (leftres x') (rightres x') 

標籤：哈斯克尔 类型类 科弗里

上一篇：如何生成具有n個點的不同大小網格的所有可能解決方案

下一篇：OSError：/usr/lib/ghc/ghc-prim-0.5.2.0/libHSghc-prim-0.5.2.0-ghc8.4.4.so：未定義符號：stg_gc_unpt_r1