ダイナミックツリーからハスケルリストへ

Question

ダイナミックツリーの要素のリストを取得したいと思います。

Iは、ノードの二つのタイプがあります二つの数字と子供/サブツリーの任意の量を記憶することができる

• Indexnodes、（いかなるサブツリーも許可されていない）数を格納することができる
• Datanodesを、。

data MultTree a = DataNode a | IndexNode a a [MultTree a] deriving Show 

t1 :: MultTree Int 
t1 = IndexNode 3 42 [IndexNode 3 15 [DataNode 3, DataNode 11, DataNode 12], IndexNode 9 42 [DataNode 42, DataNode 23]] 

dataList:: MultTree -> [DataNode] -> [Int] 
dataList[] = [] 
dataList(x:xs) = x : dataList xs 

リストには、すべてのdatanodesを含まなければなりません。したがって、dataList t1の場合、リストは[3, 11, 12, 42, 23]のようになります。

私がコードしている機能dataListは機能しません。

誰かが私がそれをどのように解決できるか考えていますか？

Answer 1

最も簡単な方法は、あなた（現代版のGHC）コンパイラがあなたのために定義することです。以下は、適切な言語拡張を設定し、希望の定義をデフォルトのtoListの定義に設定します。私は割り当てを含めましたが、通常はtoListと呼ぶだけです。

{-# Language DeriveFoldable #-} 
module MultTreeList where 

import Data.Foldable(toList) 

data MultTree a = DataNode a | IndexNode a a [MultTree a] 
    deriving (Foldable,Show) 

t1 :: MultTree Int 
t1 = IndexNode 3 42 [IndexNode 3 15 [DataNode 3, DataNode 11, DataNode 12], IndexNode 9 42 [DataNode 42, DataNode 23]] 

dataList :: MultTree a -> [a] 
dataList = toList 

タイプシグネチャに注意してください。あなたの質問はMultTree -> [DataNode] -> [Int]の署名を仮定します。これはいくつかの点で悪いです。あなたはMultiTreeの型パラメータを忘れていました。 2番目のDataNodeはタイプコンストラクタであり、タイプではありません。型シグネチャにコンストラクタを含めることはできません。これは、ビットintに1を加算関数を表すためにそのような

add1 :: Int -> 1 -> Int 

としてadd関数を指定するようになります。私が書いたような型署名を意図したと思う。

モジュールをGHCIに読み込みます。

*MultTreeList> dataList t1 
[3,42,3,15,3,11,12,9,42,42,23] 

上記の方法では、2つのコンストラクタを適切なリスト構造にマップする方法が必要です。あなたは対処する必要のある2つのパターンを持っています。

dataList (DataNode a) = ? 
dataList (IndexNode a b mts) = ?? 

私はあなたの仕事を手伝ってくれるでしょう。

dataList (DataNode a) = [a] 
dataList (IndexNode a b mts) = a : b : (??? mts) 

注??? :: [MultTree a] -> [a]