Как оценить это обобщенное абстрактное синтаксическое дерево в Haskell? - PullRequest
Новая
       33

Как оценить это обобщенное абстрактное синтаксическое дерево в Haskell?

3 голосов
/ 21 мая 2019

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

-- Instead of this
data Tree = Number Int | Word String | Operation Tree (Tree -> Tree -> Tree) Tree

-- I'd like something along the lines of this
data Tree a = Leaf a | Operation Tree (Tree -> Tree -> Tree) Tree

Это не обязательно большая практичность, но я хочу посмотреть, возможно ли это. Самое близкое, что мне удалось до сих пор, потребовало от меня возиться с понятием ГАДЦ: 

{-# LANGUAGE GADTs #-}

data Tree l where
  Leaf :: l -> Tree l
  Operation :: Tree a -> (a -> b -> c) -> Tree b -> Tree c

let fivePlus2 = Operation (Leaf 5) (+) (Leaf 2)

eval (Leaf l) = l
eval (Operation left op right) = op (eval left) (eval right)

С мыслью, что я мог бы запустить eval fivePlus2 и получить 7. Однако определение eval для Operation (этой последней строки) приводит к следующей очень неясной ошибке: 

<interactive>:187:38: error:
    • Couldn't match type ‘a’ with ‘p’
      ‘a’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree a -> a
        Actual type: Tree p -> p
    • In the first argument of ‘op’, namely ‘(eval left)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        op :: a -> b -> p (bound at <interactive>:187:22)
        left :: Tree a (bound at <interactive>:187:17)
        eval :: Tree p -> p (bound at <interactive>:187:1)

<interactive>:187:50: error:
    • Couldn't match type ‘b’ with ‘p’
      ‘b’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree b -> b
        Actual type: Tree p -> p
    • In the second argument of ‘op’, namely ‘(eval right)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        right :: Tree b (bound at <interactive>:187:25)
        op :: a -> b -> p (bound at <interactive>:187:22)
        eval :: Tree p -> p (bound at <interactive>:187:1)

Я, честно говоря, совсем не уверен, что это значит, и я немного не в себе, сначала попробовал это на F # и обнаружил, что это недостаточно выразительно. Я давно не занимался функциональным программированием, и я очень новичок в Haskell, поэтому я был бы очень признателен, если бы ответы были объяснены так, как мне было 5.

Если окажется, что оценка такого дерева невозможна, это нормально, но мне бы очень хотелось узнать, какова логика, стоящая за ним. Спасибо!

1 Ответ

13 голосов
/ 21 мая 2019

Добавление сигнатуры типа в функции верхнего уровня: 

eval :: Tree l -> l

Это обычно считается хорошей практикой, но это особенно важно для GADT, поскольку этот тип не выводится иначе.

...