Самая левая крайняя редукция (Haskell)

я получил задачу использовать самое левое внешнее сокращение для следующего выражения:

f inc expo 9 (f (*2) expo 3 1)

Inc определяется как:

 inc :: Int -> Int
 inc x = x+1

экспо определяется как:

expo :: Int -> Int
expo x = expo (x*2)

и f как:

f :: (Int->Int) -> (Int-> Int) -> Int -> Int -> Int
f g h a b = g(a-b)

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

Буду признателен за каждый совет/помощь.


haskell reduction
person Nobody    schedule 31.01.2014    source источник
comment
из вашего определения expo он никогда не прекратится   -  person DiegoNolan    schedule 31.01.2014
comment
На самом деле так и будет, поскольку expo (h в определении f) никогда не используется (т.е. никогда ни к чему не применяется).   -  person fjh    schedule 31.01.2014
comment
Это означает, что я начинаю сокращение с функции f? Значит вкл это г, экспо ч, 9 а а остальные б?   -  person Nobody    schedule 31.01.2014
comment
посмотрите на уравнение f g h a b = g(a-b) и посмотрите, какие g h a b находятся в f inc expo 9 (f (*2) expo 3 1). Это создаст выражение с использованием inc, expo, 9 и (f (*2) expo 3 1). Следующим шагом будет выполнение редукции (если хотите, замены), без которой вы не сможете вычислить g (a-b). И так до тех пор, пока вы не получите значение типа Int (или функцию, но в этом случае вы получите Int)   -  person Sassa NF    schedule 31.01.2014
comment
@fjh английский раздражает. я имел в виду, что «из вашего определения expo expo никогда не прекратится»   -  person DiegoNolan    schedule 31.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

Первая (крайняя левая, крайняя) редукция для

f inc expo 9 (f (*2) expo 3 1)

заключается в применении определения f один раз, где f g h a b = g(a-b) поэтому мы используем g как inc, a как 9 и b как (f (*2) expo 3 1), что дает

inc(9 - (f (*2) expo 3 1))

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

person not my job    schedule 31.01.2014