LINUX.ORG.RU
Форум — Talks  

КЛ калькулятор

 , , ,


0

2

есть дата тип:

data Term = S | K | I | App Term Term

нужно проверить соответствует ли Term определенной форме

правила довольно простые: 

S x y z -> x z (y z)
K x y -> x
I x -> x

например:

(App(App(App S K)I)I)

возвращает True, т.к. S KII -> KI (II) -> K II -> I

или например:

(App (App I K) (App (App K I) K))

возвращает False, т.к. (I K) ((K I )K) -> K ((K I) K), т.е. К имеет только один аргумент и не сокращается.

не могу понять как в Haskell посмотреть за скобки в рекурсии, если возвращается тип (I K или S).

суть

помогите нубу )

☆

Последнее исправление: Klymedy (всего исправлений: 3)
← Wacom-планшет с экраном в пределах 15 тыр.
Столлман о проприетарных надстройках над GCC →
Ответ на: комментарий от dmitry_malikov

ну вот ты умный напиши одну функцию

без дерева, как вернуть сокращение?

Sonsee ☆
() автор топика

dmitry_malikov

нет, подожди, я же не про преобразования вопрос задал.

есть правила, есть тип данных, как вернуть сокращение?

я понимаю хочется поиздеваться, я 3-ий день хаскелль изучаю.

Sonsee ☆
() автор топика

не могу понять как в Haskell посмотреть за скобки в рекурсии, если возвращается тип

Не распарсил.

Реализуй правила редукции с помощью pattern-matching.

Вот код, который работает с твоими примерами, но скорее всего он неправильный: 

data Term = S | K | I | App Term Term deriving (Show)

isAtomic :: Term -> Bool
isAtomic S = True
isAtomic K = True
isAtomic I = True
isAtomic _ = False

reduce :: Term -> Term
reduce (App (App (App S x) y) z) = reduce (App (reduce (App (reduce x) (reduce z)))
                                               (reduce (App (reduce y) (reduce z))))
reduce (App (App K x) y)         = reduce x
reduce (App I x)                 = reduce x
reduce a@(App x y)
    | isAtomic x && isAtomic y   = a
    | otherwise                  = reduce (App (reduce x) (reduce y))
reduce x                         = x

theNamelessOne ★★★★★
()
Последнее исправление: theNamelessOne (всего исправлений: 1)
Ответ на: комментарий от theNamelessOne

правильно сформулированный вопрос подразумевает ответ, как правило

reduce a@(App x y)
    | isAtomic x && isAtomic y   = a
    | otherwise                  = reduce (App (reduce x) (reduce y))

вот это я и не сообразил, спасибо.

Sonsee ☆
() автор топика
Ответ на: комментарий от s9gf4ult

ТС, поставь вопрос более прямее и по русскому языку.

да ну я уже понял что кроме кривляний тут никто ничего не посоветует.

Sonsee ☆
() автор топика
Ответ на: комментарий от grouzen

не знаю, может я неправильно выразился.

что я имею в виду под «посмотреть за скобки»:

есть стек, который создаётся рекурсией

к примеру мы доходим до S в этом примере:

(((S K)I)I) -> ((S K)I) -> (S K) -> S

каким образом на это месте функция может либо проверить сколько аргументов передается в S? (в этом случае 3: K I I), либо вернуть уже результат K I (I I).

вот это мне не понятно.

или в другом примере, где нужно (I K) (blabla) <- отсюда уже видно что выражение не сокращается, т.к. в I K () -> K (), т.е. в K передается один аргумент и дальше проверять не нужно. Другими словами, выражение (redex) проверять нужно на верхнем уровне (top-level), поэтому нужен «look-ahead» - или по-русски «посмотреть вперед».

я повторюсь, меня лямбда преобразования не интересуют, вопрос про код, или как именно это поведение написать.

Sonsee ☆
() автор топика
Ответ на: комментарий от Sonsee

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

grouzen ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Wacom-планшет с экраном в пределах 15 тыр.
Talks
Столлман о проприетарных надстройках над GCC →