Haskell парсинг двоичного дерева - PullRequest
Новая
       33

Haskell парсинг двоичного дерева

1 голос
/ 23 января 2020

Я узнаю о построении и разборе двоичных деревьев в Haskell и нашел пример программы, который не совсем понимаю, как работает .. Итак, код такой: 

module Main where

data TTT aa = Leaf [aa] | Node (TTT aa) (TTT aa)  deriving (Show,Eq);

a :: Num a => Integer -> Integer; 
a x = x^2; 

ff_a :: TTT Integer -> TTT Integer; 
ff_a t = mm a t; 

mm :: (Integer -> Integer) -> TTT Integer -> TTT Integer; 
mm f (Node a1 a2) = Node(mm f a1) (mm f a2); 
mm f (Leaf n) = Leaf(new_mm f n); 

new_mm :: (Integer -> Integer) -> [Integer] -> [Integer]; 
new_mm f (a:a1) = f a : new_mm f a1; 
new_mm f [] = []; 

tree =   
    Node   
        (Node   
            (Node   
                ((Leaf[16,-5,19]))
                ((Leaf[14,24,-55,27]))
            )  
            (Node   
                ((Leaf[37,11,64]))
                ((Leaf[-14,6,29]))
            )  
        )  
        (Node   
            (Node   
                ((Leaf[10,-19,22]))
                ((Leaf[3,4,5,-7]))
            )  
            (Node   
                ((Leaf[31,29,13]))
                ((Leaf[18,38,-4]))
            )  
        )  


main :: IO ();

t0 = tree      
t1 = ff_a tree 

main = do

    print t0;
    print t1;

Может кто-нибудь объяснить мне, как реально работают функции mm и new_mm? И что означает Integer -> Integer и TTT integer -> TTT integer и что это за тип данных?

1 Ответ

2 голосов
/ 23 января 2020

Код, показанный в OP, не компилируется, но его довольно легко исправить. Измените a на: 

a :: Integer -> Integer; 
a x = x^2;

(Кстати, точки с запятой являются избыточными и должны быть удалены. Это не идиоматический c Haskell - заканчивать каждую строку точкой с запятой.)

Может ли кто-нибудь объяснить мне, как на самом деле работают функции "mm" и "new_mm"?

mm зависит от new_mm, поэтому давайте начнем с этого. Распространенный способ понять, как и что делает код Haskell, - это поэкспериментировать с ним в GHCi. 

*Main> new_mm a []
[]
*Main> new_mm a [1,2,3]
[1,4,9]
*Main> new_mm (\i -> i + 1) [1,2,3]
[2,3,4]

Функция new_mm переводит каждое значение в списке ввода в соответствии с аргументом функции , Это просто встроенная функция map, реализованная с нуля и работающая только на Integer. Если вам нужно понять, как работает реализация map, я уверен, что ваш учебный ресурс Haskell содержит объяснение.

Функция mm просто «повышает» функцию отображения для работы с TTT структура данных. 

*Main> mm a (Leaf [])
Leaf []
*Main> mm a (Leaf [1,2,3])
Leaf [1,4,9]
*Main> mm (\i -> i + 1) (Leaf [1,2,3])
Leaf [2,3,4]
*Main> mm (\i -> i + 1) (Node (Leaf [1,2,3]) (Leaf [4,5,6]))
Node (Leaf [2,3,4]) (Leaf [5,6,7])

А что означает Integer -> Integer и TTT integer -> TTT integer и какой это тип данных?

Integer -> Integer указывает на функцию, которая принимает Integer в качестве ввода и которая возвращает Integer.

TTT Integer -> TTT Integer (обратите внимание, что я изменил регистр), аналогично, означает функцию, которая принимает TTT Integer значение в качестве ввода и которое возвращает TTT Integer значение.

...