Haskell: рекурсивное определение кортежа
В ней я пытаюсь создать Кривинскую Абстрактную Машину. Один из типов данных, которые мне нужно построить, — это среда. Среда строится как таковая:
У нас есть x, "Var" (это просто синоним строки) У нас есть N, «Термин» (это лямбда-терм)
Таким образом, определение среды E:
Е = (х, N, Е) · Е.
Итак, окружение — это список кортежей. Каждый кортеж содержит Var (String), A Term и список сред (который может быть пустым).
Я определяю «Env» так:
data Env = Env (Var, Term, [Env])
Для меня это выглядит так, как будто это должно работать. Однако, когда я пытаюсь использовать Env, я получаю:
*Main> ("y", Lambda "z" (Variable "z"), []) :: Env
<interactive>:166:1: error:
* Couldn't match expected type `Env'
with actual type `([Char], Term, [a0])'
* In the expression: ("y", Lambda "z" (Variable "z"), []) :: Env
In an equation for `it':
it = ("y", Lambda "z" (Variable "z"), []) :: Env
"y" - это, безусловно, [Char]
Лямбда "z" (переменная "z") определенно имеет тип Term
А пустой список — это точно список!
У меня есть ощущение, что проблема может возникнуть с пустым списком, но абсолютно необходимо, чтобы пустой список мог присутствовать в среде (это базовый случай).
Я пытался заставить это работать в течение нескольких часов, но безуспешно. Любая помощь приветствуется.
Ответы 1
data Env = Env (Var, Term, [Env])
Здесь вы определяете тип Env и конструктор данных Env. У них одинаковое имя, но конструктор данных Env — это значение типа:
ghci> :t Env
Env :: (Var, Term, [Env]) -> Env
Конструктор определяет отображение кортежей в значения Env. Его также можно использовать при сопоставлении с образцом для сопоставления значений Env с кортежами:
ghci> :t \(Env t) -> t
\(Env t) -> t :: Env -> (Var, Term, [Env])
Хитрость в том, что хотя значения типа Env изоморфны кортежам (Var, Term, [Env]), они имеют другой тип; Env. Это набор именительный падеж, а не набор структурный. Это очень полезно, когда мы хотим иметь значения, которые имеют одинаковую структуру под капотом, но отличаются в системе типов, например.
data SecondsAfterMidnight = SecondsAfterMidnight Int
data PenniesPerHour = PenniesPerHour Int
Это мешает нам сделать что-то вроде fiveCentsPerHour + oneFifteenAM.
Тем не менее, иногда вам просто нужно более удобное имя для сложного типа, и вы не хотите, чтобы оно отличалось от сложного типа. В Haskell есть псевдонимы типов для обработки этого случая. Например, String — это псевдоним типа [Char] (список символов); это два имени одного и того же типа.
Если бы он не был рекурсивным и вы не хотели возиться с конструктором, вы могли бы использовать псевдоним типа с помощью ключевого слова type:
type Env = (Var, Term, [SomethingElse])
Но вы не можете использовать псевдонимы типов для определения рекурсивных типов, поскольку они будут бесконечно расширяться во время компиляции.
Другой способ, который вы можете сделать, — отказаться от кортежа и использовать конструктор Env:
data Env = Env Var Term [Env]
Теперь конструктор Env принимает три параметра, а не кортеж.
ghci> :t Env
Env :: Var -> Term -> [Env] -> Env
Вы также можете использовать синтаксис записи для получения геттеров для различных полей:
data Env = Env { var :: Var, term :: Term, env :: [Env] }
Это может быть очень удобно:
ghci> :t var
var :: Env -> Var
ghci> :t term
term :: Env -> Term
ghci> :t env
env :: Env -> [Env]
Ах, мой плохой, я забыл, что это было рекурсивно. У вас не может быть рекурсивных псевдонимов, потому что это привело бы к бесконечным типам (Var, Term [(Var, Term, [(Var, Term, [.... Он рекурсивный, поэтому вам понадобится объявление data и конструктор.
Понятно, немного больнее, но я уверен, что смогу выстоять :) Спасибо!
@ Джимми, я не знаю точно, какие болевые точки вы находите, но есть ряд распространенных способов облегчить шаблон, например, получение Show, Eq, Functor, Foldable, которые очень часто могут сделать вашу жизнь проще.
Вау, спасибо! Использование данных и отказ от кортежа, безусловно, работает, но было бы проще, если бы он был в форме кортежа.
type Env = (Var, Term, [Env])выглядел многообещающе, но когда я пытаюсь его использовать, я получаюCycle in type synonym declarations, и он отказывается компилироваться. Я видел похожее определение вершины в другом посте, но компилятору оно, похоже, не нравится. Есть ли способ обойти это?