Haskell - Нумерация дерева подкатегорий

Question

Я готовлюсь к экзамену с непроцедурных языков. У меня есть пример тестовой задачи, и я не знаю, как ее решить.

Задача заключается в следующем:

Учитывая две древовидные структуры:

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, потому что она должна возвращать дерево и acumulated число предпорядком, но я не знаю, как это сделать.

Любые предложения приветствуются.

Answer 1

Это хорошо использовать для State monad, который заботится о потоковом значении, используемом для номера каждого узла, через рекурсивные вызовы, которые посещают каждый узел.

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

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