Haskell — предварительная нумерация дерева

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

Задача следующая:

Даны две древовидные структуры:

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

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


haskell preorder
person Vojacejo    schedule 17.06.2016    source источник
comment
Я не понимаю, зачем вам нужно ограничение Num a.   -  person melpomene    schedule 17.06.2016
comment
Я думаю, что ваша вспомогательная функция должна иметь тип numberTree' :: Tree a -> Int -> (NumTree a, Int).   -  person melpomene    schedule 17.06.2016
comment
спасибо, но я думаю, что это numberTree' :: Tree a -> Int -> NumTree a или нет?   -  person Vojacejo    schedule 17.06.2016
comment
и Num a потому что в дереве будут числа   -  person Vojacejo    schedule 17.06.2016
comment
Ваша функция numberTree не должна заботиться об элементах дерева, она должна просто добавлять числа.   -  person melpomene    schedule 17.06.2016

Ответы (2)


arrow_upward
2
arrow_downward

Это хорошее применение для монады 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)
person chepner    schedule 17.06.2016
comment
Большое спасибо за решение. Вроде работает, но в моем ghci нет State монады. Как это реализовано? - person Vojacejo; 18.06.2016
comment
@Vojacejo попробуйте haskell.org/hoogle/?hoogle=Control.Monad.State - person Will Ness; 18.06.2016

arrow_upward
3
arrow_downward

Вы можете использовать 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) []]

person Will Ness    schedule 17.06.2016