Haskell Lambda fold

У меня есть следующий алгебраический тип данных, представляющий лямбда-исчисление в Haskell:

data LExpr
    = Var String         -- variable
    | App LExpr LExpr    -- function application
    | Lam String LExpr   -- Lambda abstraction 
    deriving (Eq, Show)

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

foldr :: (α -> β-> β) -> β -> [α] -> β
foldr (#) z = go
  where
    go []     = z
    go (x:xs) = x # go xs

Итак, что я сделал до сих пор:

lfold :: (String -> a) -> (a -> a -> a) -> (String -> a -> a) -> LExpr -> a   --given by definition
lfold f z = go
  where
    go (Var _) = z            --Not sure here how to do the base case
    go (Lam v e) = v f go e

Это правильный путь? Если нет, то где я не прав и как это исправить?


string lambda fold haskell algebraic-data-types
person Dimitar    schedule 14.06.2015    source источник
comment
Взгляните на свою подпись, это не та же подпись, что и foldr, вы должны назвать переменные, которые изменились. Также не забудьте заключить конструкторы в круглые скобки. Например, v f go e имеет типы String, String -> a, LExpr -> a и LExpr, которые представляют собой бессмысленную цепочку вызовов.   -  person Guvante    schedule 14.06.2015
comment
@Guvante хорошо, тогда что соответствует подписи?   -  person Dimitar    schedule 14.06.2015
comment
stackoverflow .com/questions/16426463/   -  person Luis Casillas    schedule 15.06.2015

Ответы (1)


arrow_upward
1
arrow_downward

Я лишь дам подсказку.

Предположим, у вас есть список целых чисел следующего типа:

data List = Nil | Cons Int List

Тогда складка становится

foldr :: β -> (α -> β -> β) -> [α] -> β
foldr nil cons = go
  where
    go Nil         = nil
    go (Cons x xs) = cons x (go xs)

Обратите внимание, что после того, как я тщательно назову аргументы nil, cons, это всего лишь вопрос 1) сопоставления Nil (конструктор) с nil (параметр), 2) сопоставления Cons с cons, 3) применения go к подтермам типа List (т. е. xs) .

Для вашего типа,

data LExpr
    = Var String         -- variable
    | App LExpr LExpr    -- function application
    | Lam String LExpr   -- Lambda abstraction

мы можем использовать тот же трюк:

lfold :: (String -> a) -> (a -> a -> a) -> (String -> a -> a) -> LExpr -> a   
lfold var app lam = go
  where
    go (Var v)     = ??
    go (App e1 e2) = ??
    go (Lam v e)   = ??

Обратите внимание, как я назвал три аргумента: var, app, lam. Проверив, что произошло в типе List выше, теперь вы сможете заполнить пробелы.

person chi    schedule 14.06.2015
comment
go (Var v) = v, go (App e1 e2) = go e1 ++ go e2 и go (Lam v e) = v app go e? Я прав? И спасибо за объяснение. - person Dimitar; 14.06.2015
comment
@ user4325010 Нет, помните, мы сопоставили Nil с nil и Cons с cons. Таким образом, Var должно быть сопоставлено с... В частности, Var v должно быть сопоставлено с ... v. - person chi; 14.06.2015
comment
go (Var v) = var v, go (App e1 e2) = app (go e1) (go e2), go (Lam v e) = lam v (go e)? правильно? - person Dimitar; 14.06.2015
comment
@ user4325010 Отлично! - person chi; 14.06.2015