3

非手続き型言語の試験の準備をしています。テストタスクの例があり、それを解決する方法がわかりません。

タスクは次のとおりです。

2 つのツリー構造が与えられた場合:

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

書き込み機能

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

予約注文で番号が付けNumTree aられます。

これを試しましたが、続行する方法がわかりません。

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))

ツリーと累積された予約注文番号を返す必要があるため、このようなものを書く方法myMapはわかりませんが、これを行う方法がわかりません。

どんな提案でも大歓迎です。

4

2 に答える 2

3

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) = ....

                mapAccumL g (n+1) 木

Num a =>制約は必要ありません。ノードの値にアクセスするのではなく、ノードが運ぶものに関係なく、ノードをカウントするだけです。

> numberTree (Node1 1.1 [Node1 2.2 [ Node1 3.3 [], Nil1], Node1 4.4 [] ])
Node2 (1.1,1) [Node2 (2.2,2) [Node2 (3.3,3) [],Nil2],Node2 (4.4,4) []]

于 2016-06-17T19:34:09.530 に答える