Динамическое дерево для списка в Haskell

Question

Я хотел бы получить список элементов моего динамического дерева.

У меня есть два типа узлов:

• 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 

Список должен включать в себя все DataNode,. Поэтому для 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. Второй DataNode является конструктором типа, а не типом. Включение конструктора в подпись типа не допускается. Было бы немного как указания add функции, такие как

add1 :: Int -> 1 -> Int 

представлять собой функцию, которая добавляет один к Int. Я думаю, вы предназначались для подписи типа, как я писал.

Загрузка модуля в GHCI.

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

Неисправность вышеуказанного метода, вам нужен способ сопоставить ваши два конструктора с соответствующими конструкциями списков. У вас есть два шаблона, которые необходимо решить,

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

Я помогу вам начать работу.

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

Обратите внимание на тип подписи ??? :: [MultTree a] -> [a]