如何在Haskell中编写N-ary树遍历函数

Question

我需要遍历N-ary树,并在我按预订访问时向每个节点添加数字.我有这样定义的n-ary树:

data NT a = N a [NT a] deriving Show

示例: 如果我有以下树:

let ntree = N "eric" [N "lea" [N "kristy" [],N "pedro" [] ,N "rafael" []],N "anna" [],N "bety" []]

我想把它改造成

let ntree = N (1,"eric") [N (2,"lea") [N (3,"kristy") [],N (4,"pedro") [] ,N (5,"rafael") []],N (6,"anna") [],N (7,"bety") []]

"Preordedness"并不重要.

我想看看如何编写一个在级别之间传递值的函数,比如如何将数字传递给后继列表以及如何将更新的数字传递给父级,并将该数字传递给其他分支.

到目前为止,我已经能够编写这样的函数:

traverse :: NT String -> String
traverse (N val []) =" "++val++" "
traverse (N val list) =val++" " ++ (concat $ map  traverse list)

哪个输出

"eric lea  kristy  pedro  rafael  anna  bety "

编辑:问题是:

我该怎么写函数

numberNodes :: NT a -> NT (a,Int)

根据树的前序遍历编号节点？

我难以理解的是通过辅助数据,你能详细说明吗？

在这个具体的例子中,它是一个Int,意思是"时间"或我遍历这棵树的顺序.

Answer 1

第一次尝试:努力工作

对于n-ary树的情况,有三件事情发生:编号元素,编号树和树的编号列表.这将有助于单独对待它们.类型第一:

aNumber   :: a                -- thing to number
          -> Int              -- number to start from
          -> ( (a, Int)       -- numbered thing
             , Int            -- next available number afterwards
             )

ntNumber  :: NT a             -- thing to number
          -> Int              -- number to start from
          -> ( NT (a, Int)    -- numbered thing
             , Int            -- next available number afterwards
             )

ntsNumber :: [NT a]           -- thing to number
          -> Int              -- number to start from
          -> ( [NT (a, Int)]  -- numbered thing
             , Int            -- next available number afterwards
             )

请注意,所有三种类型共享相同的模式.当你看到你所遵循的模式时,显然巧合,你知道你有机会学到一些东西.但是现在让我们继续关注并稍后学习.

对元素进行编号很简单:将起始编号复制到输出中,并将其后续编号返回到下一个可用编辑器.

aNumber a i = ((a, i), i + 1)

对于另外两个,模式(再次出现这个词)是

1. 将输入拆分为顶级组件
2. 依次对每个组件进行编号,将数字穿过

首先使用模式匹配(在视觉上检查数据)和第二个使用where子句(抓住输出的两个部分)很容易.

对于树,顶级分割为我们提供了两个组件:元素和列表.在where子句中,我们按照这些类型的指示调用适当的编号函数.在每种情况下,"事物"输出告诉我们应该放置什么来代替"事物"输入.同时,我们将数字穿过,所以整数的起始编号是第一个组件的起始编号,第一个组件的"下一个"编号从第二个组件开始,而第二个组件的"下一个"编号是"下一个" "整数.

ntNumber (N a ants) i0  = (N ai aints, i2) where
  (ai,    i1) = aNumber   a    i0
  (aints, i2) = ntsNumber ants i1

对于列表,我们有两种可能性.空列表没有组件,因此我们直接返回它而不使用任何其他数字."cons"有两个组成部分,我们完全像以前一样,使用类型指示的相应编号函数.

ntsNumber []           i  = ([], i)
ntsNumber (ant : ants) i0 = (aint : aints, i2) where
  (aint,  i1) = ntNumber  ant  i0
  (aints, i2) = ntsNumber ants i1

我们试一试吧.

> let ntree = N "eric" [N "lea" [N "kristy" [],N "pedro" [] ,N "rafael" []],N "anna" [],N "bety" []]
> ntNumber ntree 0
(N ("eric",0) [N ("lea",1) [N ("kristy",2) [],N ("pedro",3) [],N ("rafael",4) []],N ("anna",5) [],N ("bety",6) []],7)

所以我们在那里.但我们开心吗？好吧,我不是.我有令人讨厌的感觉,我写了几次相同的类型三次和几乎相同的程序两次.如果我想为不同组织的数据(例如,你的二进制树)做更多的元素编号,我将不得不再次写同样的东西.Haskell代码中的重复模式总是错失机会:培养自我批评感并询问是否有更简洁的方法非常重要.

第二次尝试:编号和线程

我们在上面看到的两个重复模式是1.类型的相似性,2.数字线程的相似性.

如果你匹配类型以查看共同点,你会注意到它们都是

input -> Int -> (output, Int)

用于不同的输入和输出.让我们给最大的公共组件命名.

type Numbering output = Int -> (output, Int)

现在我们的三种类型

aNumber   :: a      -> Numbering (a, Int)
ntNumber  :: NT a   -> Numbering (NT (a, Int))
ntsNumber :: [NT a] -> Numbering [NT (a, Int)]

你经常在Haskell中看到这样的类型:

             input  -> DoingStuffToGet output

现在,为了处理线程,我们可以构建一些有用的工具来处理和组合Numbering操作.要查看我们需要哪些工具,请查看在对组件进行编号后如何组合输出.输出的"东西"部分总是通过将一些未编号的函数(通常是数据构造函数)应用于编号中的某些"事物"输出来构建.

为了处理这些功能,我们可以构建一个看起来很像我们的[]情况的小工具,不需要实际的编号.

steady :: thing -> Numbering thing
steady x i = (x, i)

不要被类型使它看起来好像steady只有一个参数的方式推迟:记住Numbering thing缩写一个函数类型,所以那里确实有另一个->.我们得到了

steady [] :: Numbering [a]
steady [] i = ([], i)

就像在第一行ntsNumber.

但对于其他的构造,N和(:)？问ghci.

> :t steady N
steady N :: Numbering (a -> [NT a] -> NT a)
> :t steady (:)
steady (:) :: Numbering (a -> [a] -> [a])

我们使用函数作为输出进行编号操作,并且我们希望通过更多编号操作生成这些函数的参数,从而产生一个大的整体编号操作,其中数字穿过.该过程的一个步骤是为编号生成的函数提供一个编号生成的输入.我将其定义为中缀运算符.

($$) :: Numbering (a -> b) -> Numbering a -> Numbering b
infixl 2 $$

与显式应用程序运算符的类型进行比较, $

> :t ($)
($) :: (a -> b) -> a -> b

该$$运算符是"编号申请".如果我们能够做到正确,我们的代码就变成了

ntNumber  :: NT a -> Numbering (NT (a, Int))
ntNumber  (N a ants)   i = (steady N $$ aNumber a $$ ntsNumber ants) i

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber []           i = steady [] i
ntsNumber (ant : ants) i = (steady (:) $$ ntNumber ant $$ ntsNumber ants) i

照aNumber原样(暂时).此代码仅执行数据重构,将构造函数和组件的编号过程联系在一起.我们最好给出定义,$$并确保它获得正确的线程.

($$) :: Numbering (a -> b) -> Numbering a -> Numbering b
(fn $$ an) i0 = (f a, i2) where
  (f, i1) = fn i0
  (a, i2) = an i1

在这里,我们的旧线程模式完成一次.每个fn和an是一个函数,期望一个起始编号,而整个fn $$ sn是一个函数,它获取起始编号i0.我们通过线程编号,首先收集函数,然后收集参数.然后我们进行实际应用并交回最后的"下一个"号码.

现在,请注意,在每行代码中,i输入都作为参数输入到编号过程中.我们可以通过谈论过程而不是数字来简化这段代码.

ntNumber  :: NT a -> Numbering (NT (a, Int))
ntNumber  (N a ants)   = steady N $$ aNumber a $$ ntsNumber ants

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber []           = steady []
ntsNumber (ant : ants) = steady (:) $$ ntNumber ant $$ ntsNumber ants

读这段代码的一种方法是过滤掉所有的Numbering,steady和$$用途.

ntNumber  :: NT a -> ......... (NT (a, Int))
ntNumber  (N a ants)   = ...... N .. (aNumber a) .. (ntsNumber ants)

ntsNumber :: [NT a] -> ......... [NT (a, Int)]
ntsNumber []           = ...... []
ntsNumber (ant : ants) = ...... (:) .. (ntNumber ant) .. (ntsNumber ants)

并且你看它看起来像是一个前序遍历,在处理元素后重建原始数据结构.我们正在使用提供的值做正确的事情,steady并且$$正确地组合了这些过程.

我们可以尝试做同样的事情 aNumber

aNumber  :: a -> Numbering a
aNumber a = steady (,) $$ steady a $$ ????

但这????是我们实际需要的数字.我们可以建立一个适合那个洞的编号过程:一个编号过程,发出下一个数字.

next :: Numbering Int
next i = (i, i + 1)

这是编号的本质,"东西"输出是现在使用的数字(这是起始编号),"下一个"编号输出是后面的编号.我们可以写

aNumber a = steady (,) $$ steady a $$ next

这简化为

aNumber a = steady ((,) a) $$ next

在我们的过滤视图中,就是这样

aNumber a = ...... ((,) a) .. next

我们所做的就是提出"编号过程"的想法,并且我们已经构建了正确的工具来对这些过程进行普通的函数式编程.线程模式变成steady和的定义$$.

编号不是唯一以这种方式工作的东西.试试这个...

> :info Applicative
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

...而且你还得到更多的东西.我只是想提醒大家注意的类型pure和<*>.他们很像steady和$$,但他们不只是为Numbering.Applicative是以这种方式工作的每种过程的类型类.我不是说" Applicative现在就学习!",只是建议一个旅行方向.

第三次尝试:类型定向编号

到目前为止,我们的解决方案针对一个特定的数据结构NT a,并[NT a]显示为辅助概念,因为它已被用于NT a.如果我们一次只关注一个类型的层,我们可以使整个事情更加即插即用.我们根据编号树来定义编号树的列表.在一般情况下,我们知道如何编号列表的东西,如果我们知道如何编号的每一个项目的东西.

如果我们知道如何数量a来获得b,我们应该能够数的列表中a得到一个列表中b.我们可以抽象出"如何处理每个项目".

listNumber :: (a -> Numbering b) -> [a] -> Numbering [b]
listNumber na []       = steady []
listNumber na (a : as) = steady (:) $$ na a $$ listNumber na as

现在我们旧的树名单编号功能就变成了

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber = listNumber ntNumber

这几乎不值得命名.我们可以写

ntNumber :: NT a -> Numbering (NT (a, Int))
ntNumber (N a ants) = steady N $$ aNumber a $$ listNumber ntNumber ants

我们可以为树木本身玩同样的游戏.如果你知道如何编号,你知道如何编号树的东西.

ntNumber' :: (a -> Numbering b) -> NT a -> Numbering (NT b)
ntNumber' na (N a ants) = steady N $$ na a $$ listNumber (ntNumber' na) ants

现在我们可以做这样的事情

myTree :: NT [String]
myTree = N ["a", "b", "c"] [N ["d", "e"] [], N ["f"] []]

> ntNumber' (listNumber aNumber) myTree 0
(N [("a",0),("b",1),("c",2)] [N [("d",3),("e",4)] [],N [("f",5)] []],6)

在这里,节点数据现在本身就是一个事物列表,但我们已经能够单独编号.我们的设备更具适应性,因为每个组件都与该类型的一层对齐.

现在,试试这个:

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

这是一个可怕的很多像我们刚刚做的事情,那里f是Numbering和t有时名单,有时树木.

本Traversable类可捕获意味着什么,是一个类型,前者可以让你线程某种过程,通过存储的元素.同样,您使用的模式非常普遍并且已被预料到.学习使用traverse可以节省大量的工作.

最后...

...你将会知道Numbering在库中已经存在的工作已经存在:它被调用State Int并且它属于Monad类,这意味着它也必须在Applicative类中.抓住它,

import Control.Monad.State

并且开始状态进程的操作与其初始状态一样,就像我们的输入一样0,是这样的:

> :t evalState
evalState :: State s a -> s -> a

我们的next经营成了

next' :: State Int Int
next' = get <* modify (1+)

get访问状态的进程在哪里,modify进行改变状态的进程,<*意味着"但也做".

如果您使用语言扩展名pragma启动文件

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

你可以像这样声明你的数据类型

data NT a = N a [NT a] deriving (Show, Functor, Foldable, Traversable)

和Haskell会traverse为你写信.

你的程序然后变成一行......

evalState (traverse (\ a -> pure ((,) a) <*> get <* modify (1+)) ntree) 0
--                  ^ how to process one element ^^^^^^^^^^^^^^^
--         ^ how to process an entire tree of elements ^^^^^^^^^
--        ^ processing your particular tree ^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- ^ kicking off the process with a starting number of 0 ^^^^^^^^^^^^^^^^

......但旅途到一条线涉及到很多的"装瓶模式"的步骤,这需要一些(希望奖励)学习.