Правильный поворот дерева в Haskell: как это работает? - PullRequest
Новая
       23

Правильный поворот дерева в Haskell: как это работает?

2 голосов
/ 10 июня 2010

Я не знаю синтаксиса haskell, но я знаю некоторые концепции FP (например, алгебраические типы данных, сопоставление с образцом, функции высшего порядка и т. Д.).

Может кто-нибудь объяснить, что означает этот код:

data Tree ? = Leaf ? | Fork ? (Tree ?) (Tree ?)

rotateR tree = case tree of
  Fork q (Fork p a b) c -> Fork p a (Fork q b c)

Как я понимаю, первая строка - это что-то вроде объявления типа дерева (но я точно не понимаю).Вторая строка включает в себя сопоставление с образцом (я также не понимаю, зачем нам здесь использовать сопоставление с образцом).И третья строка делает что-то абсолютно нечитаемое для разработчика, не использующего Haskell.Я нашел определение Форка как fork (f,g) x = (f x, g x), но я больше не могу двигаться дальше.

Ответы [ 2 ]

7 голосов
/ 10 июня 2010

Прежде всего определение типа данных должно содержать не вопросительные знаки, а обычные буквы: 

data Tree a = Leaf a | Fork a (Tree a) (Tree a)

Определяет тип Tree, который содержит элементы некоторого не указанного типа a. Это либо дерево Leaf, содержащее элемент типа a, либо дерево Fork, содержащее также элемент типа a и два поддерева. Поддеревья - это Tree структуры, которые содержат элементы типа a.

Важно отметить, что Haskell использует круглые скобки исключительно для группировки, как в 2 * (2+3), а не для указания вызывающих функций. Для вызова функций параметры просто пишутся после имени функции, разделяются пробелами, как в sin 30 или compare "abc" "abd".

В операторе case часть слева от -> - это совпадение с шаблоном, часть справа - результат функции, если дерево действительно имеет форму, указанную слева. Шаблон Fork q (Fork p a b) c совпадает, если дерево является Fork (это Fork из определения типа данных), а его первое поддерево является другим Fork. Строчные буквы - это всего лишь переменные, фиксирующие совпадение различных частей древовидной структуры. Таким образом, p будет элементом, содержащимся в поддереве, a будет первой ветвью поддеревьев и b второй.

Правая сторона ->, Fork p a (Fork q b c), теперь строит новое дерево из этих частей, сопоставленных в сопоставлении с образцом. Переменные в нижнем регистре - это все совпадающие слева части дерева, а Fork - конструкторы из определения типа данных. Он строит дерево, которое является Fork и имеет второе поддерево, которое также является Fork (часть в скобках). Остальные части этого дерева - это только те части дерева, которые были «распущены» на левой стороне.

3 голосов
/ 10 июня 2010

Я думаю, вы неправильно поняли Форка.Это не функция, а конструктор для дерева типов.По сути, это узел в структуре данных дерева ... Каждый узел в дереве является либо листом (со значением), либо вилкой (со значением и двумя подузлами).

Используется сопоставление с образцомпреобразовать структуру.Моя ASCII-графика недостаточно хороша, чтобы дать вам рисунок, но она как бы сдвигает «левые узлы» вверх и «правые узлы» вниз.

Примечание: я говорю, что вы, возможно, неправильно понимаете Fork, потому что fork (f,g) x = (f x, g x) это нечто совершенно другое.В данном случае это функция более высокого порядка, не имеющая ничего общего с вашей древовидной структурой.

Надеюсь, это поможет :), Карл

...