ハスケル - 予約番号ツリーの番号

Question

私は非手続き型言語から私の試験を準備しています。私はテストのタスクの例を持っており、私はそれを解決する方法を知らない。

タスクは以下の通りです：行きがけにNumTree aに番号が付け返します

data Tree a = Nil1 | Node1 a [Tree a] 
data NumTree a = Nil2 | Node2 (a,Int) [NumTree a] 

書き込み機能

numberTree :: Num a => Tree a -> NumTree a 

：

は2つのツリー構造を考えます。

私はこれを試しましたが、続ける方法はわかりません。

numberTree tree = numberTree' tree 1 

numberTree' :: Num a => Tree a -> Int -> NumTree a 
numberTree' Nil1 _ = Nil2 
numberTree' (Node1 num list) x = (Node2 (num,x) (myMap x numberTree list)) 

私はそれが木とacumulated行きがけの数を返す必要がありますので、このmyMapような何かを書く方法を知らないが、私はこれを行う方法を知りません。

ご提案は大歓迎です。

Answer 1

これはのための良好な使用でありますStateモナドは、各ノードにアクセスする再帰呼び出しによって各ノードに番号を付けるために使用される値をスレッド化します。

import Control.Monad 
import Control.Monad.State 

data Tree a = Nil1 | Node1 a [Tree a] deriving (Show) 
data NumTree a = Nil2 | Node2 (a,Int) [NumTree a] deriving (Show) 

numberTree :: Tree a -> NumTree a 
numberTree Nil1 = Nil2 
numberTree tree = evalState (numberTree' tree) 0 

-- The state stores the value used to number the root 
-- of the current tree. Fetch it with get, and put back 
-- the number to use for the next root. 
-- numberTree' is then used to number each child tree 
-- in order before returning a new NumTree value. 

numberTree' :: Tree a -> State Int (NumTree a) 
numberTree' Nil1 = return Nil2 
numberTree' (Node1 root children) = do rootNum <- get 
             put (rootNum + 1) 
             newChildren <- mapM numberTree' children 
             return (Node2 (root, rootNum) newChildren) 

Answer 2

あなたはあなたの利点にここmapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])を使用することができます。

mapAccumL機能はmapとfoldlの組み合わせのように振る舞います。リストの各要素に関数を適用し、累積パラメータを左から右へ渡し、この累算器の最終値を新しいリストとともに返します。

マッチング線を接続しようとし、種類を見てみると、主な機能は、

import Data.List (mapAccumL) 

data Tree a = Nil1 | Node1 a [Tree a] deriving Show 
data NumTree a = Nil2 | Node2 (a,Int) [NumTree a] deriving Show 

numberTree :: Tree a -> NumTree a 
numberTree tree = tree2 
    where 
    (_, [tree2]) = mapAccumL g 1 [tree] 
    g n Nil1 = (n, Nil2) 
    g n (Node1 x trees) = (z, Node2 (x,n) trees2) 
     where 
     (z, trees2) = .... 

               ようになりますmapAccumLg（n + 1）個の木

Num a =>という制約は必要ありません。あなたはノードの値を訪問していない、あなただけに関係なく、彼らが運ぶもののノードを数える：

> numberTree（ノード1 1.1 [ノード1 2.2 [ノード1 3.3 []、Nil1]、ノード1 4.4 []]）
ノード2（1.1,1）ノード2（2,2,2-）ノード2（3.3,3）[]、Nil2]、ノード2（4.4,4）[]