Мне не удалось прочитать RWH; и не один, чтобы бросить курить, я заказал Haskell: Craft of Functional Programming. Теперь мне интересно об этих функциональных доказательствах на стр. 146. В частности, я пытаюсь доказать 8.5.1 sum (reverse xs) = sum xs
. Я могу сделать некоторые доказательства индукции, но потом я застрял.
ССЫЛ:
sum ( reverse xs ) = sum xs
БАЗА:
sum ( reverse [] ) = sum []
Left = sum ( [] ) (reverse.1)
= 0 (sum.1)
Right = 0 (sum.1)
ИНДУКЦИЯ:
sum ( reverse (x:xs) ) = sum (x:xs)
Left = sum ( reverse xs ++ [x] ) (reverse.2)
Right = sum (x:xs)
= x + sum xs (sum.2)
Итак, теперь я просто пытаюсь доказать, что Left
sum ( reverse xs ++ [x] )
равно Right
x + sum xs
, но это не слишком далеко от того места, где я начал sum ( reverse (x:xs) ) = sum (x:xs)
.
Я не совсем уверен, почему это нужно доказать, кажется вполне разумным использовать символическое доказательство reverse x:y:z = z:y:x
(через defn), а потому, что + является коммутативным (arth), то reverse 1+2+3 = 3+2+1
,