LINUX.ORG.RU

История изменений

Исправление theNamelessOne, (текущая версия) :

не могу понять как в 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, :

не могу понять как в 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