Сопоставление с образцом при реализации лямбда-исчисления в Haskell - PullRequest
Новая
       20

Сопоставление с образцом при реализации лямбда-исчисления в Haskell

0 голосов
/ 26 марта 2020

Я хочу написать функцию, которая будет собирать имена переменных, которые использовались в термине лямбда-исчисления, как в качестве переменной, так и в лямбда-абстракции.

Например, в коде я получу следующий вывод: 

  *Main> used example
         ["a","b","x","y"]

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

import Data.Char
import Data.List

type Var = String

data Term =
    Variable Var
  | Lambda   Var  Term
  | Apply    Term Term

example :: Term
example = Lambda "a" (Lambda "x" (Apply (Apply (Lambda "y" (Variable "a"))
                                               (Variable "x"))
                                        (Variable "b")))

-- I'll use this function to merge two ordered lists together:

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
    | x == y    = x : merge xs ys
    | x <= y    = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

used :: Term -> [Var]
used [] = []
used Variable_ = _
used Lambda_ = _
used Apply_ = _

Это явно не правильно.

Как мне собрать имена переменных и добавить их в список? Если сопоставление с образцом и подстановочные знаки не верны, пожалуйста, можете ли вы подсказать, как я мог go об этом?

1 Ответ

2 голосов
/ 27 марта 2020

То есть used - это функция Term -> [Var]. И поэтому, чтобы написать used в стиле сопоставления с шаблоном, нам нужно подготовить кейс для каждого из различных способов быть Term. Глядя на определение Term, мы видим, что есть 3 способа быть Term: быть переменной, лямбда-выражением или приложением. В частности, быть пустым списком ([]) не является способом быть Term, поэтому этот случай должен быть удален.

Далее давайте рассмотрим синтаксис сопоставления с образцом. Это должно выглядеть следующим образом: 

used :: Term -> [Var]
used (Variable var) = ...
used (Lambda var term) = ...
used (Apply term1 term2) = ...

Обратите внимание на круглые скобки вокруг каждого набора конструктора данных и аргументов. Также обратите внимание, что переменные в Haskell должны начинаться со строчных букв. В заключение отметим, что мы на самом деле не написали ни одного из корпусов дел для used. Вышеуказанное не является действительным Haskell.

Давайте go рассмотрим, как заполнить все правые части этих случаев. Пока мы делаем это, давайте помнить, что used предназначен для возврата упорядоченного списка Var без повторов. Большая часть этого не фиксируется в типе used.

Случай Variable: 

used (Variable var) = ...

Так что правая часть здесь должна быть списком Var. Проверяя объявление Term и Variable, мы видим, что var должно быть Var. Таким образом, на самом деле единственным вариантом реализации является: 

used (Varable var) = [var]

Случай Lambda 

used (Lambda var term) = ...

Итак, снова проверяя объявление типа Term, мы видим, что var Var и term Term. Может быть, поэтому мы использовали эти имена переменных;). Таким образом, некоторые переменные появляются в var, а некоторые переменные появляются в term. Если бы мы знали все эти переменные, мы могли бы объединить эти результаты с merge. Для var мы можем сделать то же самое, что и в случае Variable. Для term нам нужен способ превратить Term в переменную или список переменных. К счастью, у нас есть такой способ. Это функция, которую мы сейчас определяем: used! Таким образом, мы можем записать этот случай как: 

used (Lambda var term) = merge [var] (used term)

Может показаться немного глупым использовать merge для объединения одноэлементного списка в другой список, но нам нужно сохранить результат в порядке, а merge - это молоток, который у нас есть, поэтому мы превратили эту проблему в гвоздь.

* * * * * * * * * * * * * * * * * * * * * '' * '' *. У нас есть used (Apply term1 term2) = ... term1 и term2 Term. Мы извлечем переменные из каждой из них, используя used, и объединим их вместе, используя merge. used (Apply term1 term2) = merge (used term1) (used term2) В целом это дает реализацию used: used :: Term -> [Var] used (Variable var) = [var] used (Lambda var term) = merge [var] (used term) used (Apply term1 term2) = merge (used term1) (used term2) с *Main> used example ["a","b","x","y"] по желанию.

...