Описание тега equational-reasoning

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

Понимание различных сгибателей

Я понимаю простые фолд-заявления вроде foldr (+) 0 [1,2,3] Однако у меня возникли проблемы с более сложными инструкциями foldr, а именно с теми, которые принимают 2 параметра в функции, и с / и - вычислениями. Может ли кто-нибудь объяснить шаги, кот…
21 апр '14 в 02:03
1 ответ

Отслеживание "состояния" при написании доказательств равенства, представляющих собой длинные цепочки транзитивно связанных шагов

Я написал следующее доказательство в Идрисе: n : Nat n = S (k + k) lemma: n * n = ((k * n) + k) + (1 + (((k * n) + k) + 0)) lemma = sym $ rewrite plusZeroRightNeutral ((k * n) + k) in rewrite plusAssociative ((k * n) + k) 1 ((k * n) + k) in rewrite …
03 окт '17 в 19:04
0 ответов

Проблемы с эквивалентными доказательствами и разрешением интерфейса в Idris

Я пытаюсь смоделировать доказательства эквациональных рассуждений в стиле Агды для сетоидов (типов с отношением эквивалентности). Моя установка выглядит следующим образом: infix 1 :=: interface Equality a where (:=:) : a -> a -> Type interface…
15 янв '17 в 19:18
1 ответ

Отображение строгой или ленивой функции

(head . map f) xs = (f . head) xs Это работает для каждого списка xs, когда f строгое. Кто-нибудь может дать мне пример, почему с нестрогим f это не работает?
29 авг '16 в 01:26
1 ответ

Докажите транзитивность в семантике Хаскеля

Я изучаю семантику Haskell, и там я столкнулся с этим вопросом: Я попробовал это, но все еще не могу сделать ответ. Будет здорово, если кто-нибудь объяснит мне, как это доказать. Спасибо.
14 авг '16 в 07:32
3 ответа

Использую ли я обоснованные рациональные рассуждения об определении фильтра в терминах Foldr?

Хорошо, это определение функции фильтра с использованием foldr: myFilter p xs = foldr step [] xs where step x ys | p x = x : ys | otherwise = ys так, например, скажем, у меня есть эта функция: myFilter odd [1,2,3,4] так будет: foldr step [] [1,2,3,4…
02 фев '10 в 16:10
3 ответа

Как Haskell оценивает эту функцию, определенную при частичном применении?

Я пытаюсь понять, как Haskell оценивает pp1 [1,2,3,4] получить [(1,2),(2,3),(3,4)] Вот: 1. xnull f [] = [] 2. xnull f xs = f xs 3. (/:/) f g x = (f x) (g x) 4. pp1 = zip /:/ xnull tail Я начинаю так: a) pp1 [1,2,3,4] = (zip /:/ xnull tail) [1,2,3,4]…
25 апр '14 в 17:39
1 ответ

Доказать равенство двух определений функций индуктивно

Как сделать индукцию, чтобы установить утверждение moll n = doll n, с moll 0 = 1 --(m.1) moll n = moll ( n-1) + n --(m.2) doll n = sol 0 n --(d.1) where sol acc 0 = acc +1 --(d.2) sol acc n = sol ( acc + n) (n-1) -- ? (d.2) Я пытался доказать базовы…
25 янв '16 в 13:38
1 ответ

Как доказать этот код на Haskell с помощью эквациональных рассуждений

Я нашел это упражнение на уравнительных рассуждениях и доказательствах в Хаскеле. Дан следующий код: type Stack = [Int] type Code = [Op] data Op = PUSH Int | ADD deriving (Show) -- -- Stack machine -- exec :: Code -> Stack -> Stack exec [ ] s …
31 май '16 в 14:23
2 ответа

Доказательство по индукции с несколькими списками

Я слежу за лекцией "Функциональное программирование в Scala" на Coursera, и в конце видео 5.7 Мартин Одерский просит индуктивно доказать правильность следующего уравнения: (xs ++ ys) map f = (xs map f) ++ (ys map f) Как обрабатывать доказательства п…
22 май '15 в 23:25
2 ответа

Haskell - Как преобразовать максимум (xs ++ map (x+) xs) в max (максимум xs) (x + максимум xs)

Один из упражнений в "Мышление функционально с Haskell" о том, как сделать программу более эффективной с использованием закона слияния. У меня возникли проблемы при попытке повторить ответ. Часть расчета требует, чтобы вы преобразовали maximum (xs +…
02 дек '14 в 23:21
1 ответ

Как Haskell оценивает эту функцию, которая отменяет интеркаляцию списка?

Я пытаюсь понять, как Haskell оценивает sep [1, 2, 3, 4, 5] получить ([1, 3], [2, 4, 5]) где: sep [ ] = ([ ], [ ]) sep [x] = ([ ], [x]) sep (x1:x2:xs) = let (is, ps) = sep xs in (x1:is, x2:ps) Я начинаю так: sep [1, 2, 3, 4, 5] = let (is, ps) = sep …
22 апр '14 в 23:38
3 ответа

Haskell: Расширитель уравнений 1+(1+(1+(1+(…))))=∞

Существует ли расширитель уравнений для Haskell? Что-то вроде http://foldr.com/: 1+(1+(1+(1+(…))))=∞ Я новичок в Хаскеле. У меня проблемы с пониманием того, почему одни уравнения предпочтительнее других. Я думаю, что это помогло бы, если бы я мог ви…
10 дек '10 в 00:52
0 ответов

acl2 эквациональное рассуждение, доказывающее равенство

Я пытаюсь доказать, что следующая функция верна, и у меня возникают проблемы с ее выяснением, хотя это кажется очевидным! (implies (and (listp x) (listp y)) (equal (app (rev x) (rev y)) (rev (app x y)))) при этом мне просто нужно показать, что (app …
15 мар '14 в 19:54
1 ответ

Reduce(X + Y, XS) и сумма (XS) не эквивалентны в Python?

Однако я ожидаю, что эти два значения будут означать одно и то же с функциональной точки зрения: x = [1, 2, 3] y = ['a', 'b', 'c'] reduce(lambda x, y: x + y, zip(x, y)) # works sum(zip(x, y)) # fails Почему sum терпеть неудачу здесь?
20 фев '15 в 09:08
3 ответа

Можно ли использовать церковные кодировки, не нарушая уравнивания?

Имейте в виду эту программу: {-# LANGUAGE RankNTypes #-} import Prelude hiding (sum) type List h = forall t . (h -> t -> t) -> t -> t sum_ :: (Num a) => List a -> a sum_ = \ list -> list (+) 0 toList :: [a] -> List a toList =…
11 авг '15 в 00:45
2 ответа

Результат оценки функции

Я пытаюсь оценить вручную fc [f1, f2] (\x -> 2) 3 но я не понимаю, как сопоставить три параметра: [f1, f2], (\x -> 2) и 3 с определением функции, любая помощь? Определение функции: fc xss = \f -> let ope x y = x . f . y in foldr1 ope xss f1, f…
25 апр '14 в 21:20
1 ответ

Индукция в списках - Доказательство Сильной Собственности (Haskell)

Я сразу скажу, что это для задания, и я не ищу ответа - просто какое-то направление, так как я работаю над этим уже довольно давно. Дана следующая хвостово-рекурсивная функция суммы: sumTR [ ] acc = acc sumTR (x:xs) acc = sumTR xs (x + acc) по индук…
27 авг '16 в 10:24
1 ответ

Если return a = return b, тогда a=b?

Можете ли вы доказать, что если return a = return b затем a=b? Когда я использую =Я имею в виду в смысле законов и доказательств, а не Eq классовый смысл. Кажется, каждая монада, которую я знаю, удовлетворяет это, и я не могу придумать правильную мо…
25 янв '16 в 23:24
2 ответа

Haskell - Как преобразовать сумму карты (map (x:) xss) в карту (x+) (сумма карты xss)

Читая "Мышление функционально с Haskell", я натолкнулся на часть расчета программы, которая требовала, чтобы map sum (map (x:) xss) быть переписан как map (x+) (map sum xss) Интуитивно я знаю, что это имеет смысл... если у вас есть несколько списков…
20 ноя '14 в 19:52