Трансформация лыж, как программировать на функциональном языке - PullRequest
Новая
       26

Трансформация лыж, как программировать на функциональном языке

3 голосов
/ 21 января 2011

Я сталкиваюсь со следующим кодом Пролога. Выражение [X] >> Y стоит для лямбда-выражения лямбда X.Y. Код устраняет лямбду и дает комбинаторное выражение над S, K и I: 

convert([X]>>Y,'I') :- X==Y, !.
convert([X]>>Y,apply('K',Y)) :- var(Y), !.
convert([X]>>([Y]>>Z),R) :-
     convert([Y]>>Z,H), convert([X]>>H,R).
convert([X]>>apply(Y,Z),apply(apply('S',S),T)) :-
     convert([X]>>Y,S), convert([X]>>Z,T).
convert([_]>>Y,apply('K',Y)).

Вот пример, как это работает: 

 ?- convert([X]>>([Y]>>apply(Y,X)),R).
 R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
  apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))

Предположим, я хотел бы закодировать то же самое преобразование в Haskell, ML или подобное, аналогичное, похожее. Как я могу это сделать? Могу ли я использовать доступные лямбда-выражения в функциональном языке программирования напрямую? Или я должен регресс к мета-программам?

С наилучшими пожеланиями

P.S .: Приведенный выше код не является преобразованием SKI, которое приводит к очень короткому Лыжные выражения. Возможен лучший код, который проверяет наличие связанная переменная в теле лямбда-выражения.

Ответы [ 2 ]

4 голосов
/ 21 января 2011

Ваш код пролога можно почти дословно перевести в соответствие шаблонам ML или Haskell.Конечно, вам нужно определить свой собственный ADT для лямбда-выражений.А для наиболее оптимального набора комбинаторов и преобразования для этого набора я бы рекомендовал обратиться к http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

1 голос
/ 21 января 2011

Вы можете напрямую использовать выражения lamdba. В Хаскеле: 

i x = x
k x = \y -> x
s x y z = x z $ y z

r = s (s (k s) (k i)) (s (k k) i)

-- r 3 (+5) -> 8

(обратите внимание, что я не знал о SKI, чтобы знать, этот фрагмент - прямое преобразование определений в Википедии в Haskell; он работает, но проверьте, правильно ли он концептуально)

...