Функциональные доказательства (Haskell)
Я перестал работать при чтении RWH; и не один для выхода я заказал Haskell: Ремесло Функционального программирования. Теперь мне любопытно на предмет этих функциональных доказательств на странице 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)
Таким образом, теперь я просто пробую ot, доказывают это 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,
4 ответа
sum (reverse []) = sum [] -- def reverse
sum (reverse (x:xs)) = sum (reverse xs ++ [x]) -- def reverse
= sum (reverse xs) + sum [x] -- sum lemma below
= sum (reverse xs) + x -- def sum
= x + sum (reverse xs) -- commutativity assumption!
= x + sum xs -- inductive hypothesis
= sum (x:xs) -- definition of sum
Однако, существуют базовые предположения об ассоциативности и коммутативности, которые не являются строго обоснованными, и это не будет работать должным образом для ряда числовых типов, таких как Float и Double, где эти предположения нарушаются.
Лемма: sum (xs ++ ys) == sum xs + sum ys с учетом ассоциативности (+)
Доказательство:
sum ([] ++ ys) = sum ys -- def (++)
= 0 + sum ys -- identity of addition
= sum [] ++ sum ys -- def sum
sum ((x:xs) ++ ys) = sum (x : (xs ++ ys)) -- def (++)
= x + sum (xs ++ ys) -- def sum
= x + (sum xs + sum ys) -- inductive hypothesis
= (x + sum xs) + sum ys -- associativity assumption!
= sum (x:xs) + sum ys -- def sum
По сути, вам нужно показать, что
sum (reverse xs ++ [x]) = sum (reverse xs) + sum [x]
, что затем легко приводит к
= x + sum (reverse xs)
= x + sum xs -- by inductive hyp.
Проблема в том, чтобы показать, что sum распределяется по конкатенации списков.
Используйте определение суммы, чтобы разбить (сумма обратная xs ++[x]) на x + сумма(обратная(xs)), и, используя индуктивную гипотезу, вы знаете, что сумма(обратная(xs)) = сумма(xs). Но я согласен, индукция - это излишество для такой проблемы.
Думаю, вы здесь и застряли. Вам нужно доказать лемму, которая гласит
sum (xs ++ ys) == sum xs + sum ys
. Чтобы доказать этот закон, вы должны предположить, что сложение ассоциативно, что верно только для целых и рациональных чисел.
Тогда вам также нужно будет предположить, что сложение коммутативно, что верно для целых и рациональных чисел, но также и для чисел с плавающей запятой.
Отступление: Мне кажется, очень странным кажется стиль ваших доказательств. Я думаю, вам будет легче написать такие доказательства, если вы воспользуетесь стилем из книги Грэма Хаттона .