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

Question

Существует ли расширитель уравнений для Haskell?

Что-то вроде http://foldr.com/: 1+(1+(1+(1+(…))))=∞

Я новичок в Хаскеле. У меня проблемы с пониманием того, почему одни уравнения предпочтительнее других. Я думаю, что это помогло бы, если бы я мог видеть расширенные уравнения.

Например я нашел foldr против foldl сначала трудно понять, пока я не увидел, что они расширились.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z xs = go xs
             where
               go []     = z
               go (y:ys) = y `k` go ys

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

Из определений я вижу, что foldr расширяется так:

foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->

а также foldl расширяется так:

foldl (+) 0 [1..1000000] -->
foldl (+) (foldl (+) 0 [1]) [2..1000000]) --> 
foldl (+) (foldl (+) (foldl (+) 0 [1])) [3..1000000]) --> 

или из Haskell Wiki на foldr fold foldl ':

let z1 =  0 + 1
in foldl (+) z1 [2..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
in foldl (+) z2 [3..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
in foldl (+) z3 [4..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
in foldl (+) z4 [5..1000000] -->

Однако у меня проблемы с большими уравнениями, которые понимают, почему все работает так, как они работают в Хаскеле. Например, первая функция сита использует 1000 фильтров, а вторая функция сита занимает всего 24, чтобы найти 1001 простое число.

primes = sieve [2..]
   where
    sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] 



primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]  
                                    -- or:  filter ((/=0).(`rem`p)) t
                      where (h,~(_:t)) = span (< p*p) xs

Haskell Wiki на простых числах

Я потратил много времени на разработку и расширение вручную. Я пришел, чтобы понять, как это работает. Тем не менее, автоматизированный инструмент для расширения некоторых выражений значительно улучшит мое понимание Haskell.

Кроме того, я думаю, что это также может помочь в вопросах, которые направлены на оптимизацию кода на Haskell:

• Оптимизация кода на Haskell
• Помогите оптимизировать мой код на Haskell - вычислите сумму всех простых чисел ниже двух миллионов

Есть ли инструмент для расширения выражений на Haskell?

Answer 1

Дэвид В. Спасибо за эти ссылки. Repr определенно стоит добавить в мой ящик для инструментов. Я хотел бы добавить несколько дополнительных библиотек, которые я нашел полезными.

HackageDB: трассировка (по состоянию на 12 декабря 2010 г.)

• Библиотека и программа ghc-events: Библиотека и инструмент для анализа файлов.eventlog из GHC
• библиотека капота: отладка путем наблюдения на месте
• Библиотека hpc-strobe: сгенерированные Hpc стробоскопы для работающей программы на Haskell
• Программа hpc-tracer: Tracer с интерфейсом AJAX

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

капот

main = runO ex9

ex9 = print $ observe "foldl (+) 0 [1..4]" foldl (+) 0 [1..4]

выходы

10

-- foldl (+) 0 [1..4]
  { \ { \ 0 1  -> 1
      , \ 1 2  -> 3
      , \ 3 3  -> 6
      , \ 6 4  -> 10
      } 0 (1 : 2 : 3 : 4 : []) 
       -> 10
  }

Я не знал о библиотеке Hackage (поскольку я только вхожу в Haskell). Это напоминает мне о CPAN Perl. Спасибо за предоставление этих ссылок. Это отличный ресурс.

Answer 2

Это ни в коем случае не является полным ответом на ваш вопрос, но я нашел беседу в Haskell-Cafe, в которой есть несколько ответов:

http://www.haskell.org/pipermail/haskell-cafe/2010-June/078763.html

Этот поток ссылается на этот пакет:

http://hackage.haskell.org/package/repr который в соответствии со страницей "позволяет отображать перегруженные выражения в их текстовое представление"

Приведенный пример:

*Repr> let rd = 1.5 + 2 + (3 + (-4) * (5 - pi / sqrt 6)) :: Repr Double
*Repr> show rd
"fromRational (3 % 2) + 2 + (3 + negate 4 * (5 - pi / sqrt 6))"

Answer 3

Это ответ на незаданный вопрос, представьте его как длинный комментарий.

(Пожалуйста, уменьшите только ниже 0, если вы думаете, что он не подходит. Я уберу его потом.)

---

Как только вы станете немного опытнее, вы больше не захотите видеть, как все расширяется. Вы захотите понять, КАК все это работает, что заменяет вопрос, ПОЧЕМУ это работает; вы больше не выиграете, просто наблюдая за тем, как он расширяется.

Способ анализа кода намного проще, чем вы думаете: просто пометьте каждый параметр / переменную как "оцененный", "не оцененный" или "подлежащий оценке", в зависимости от развития их причинных связей.

Два примера:

---

1.) выдумки

Список всех чисел Фибоначчи

fibs :: (Num a) => [a]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Первые два элемента уже оценены; Итак, пометьте 3-й элемент (который имеет значение 2) как подлежащий оценке, а все остальные - как неоцененные. Тогда 3-й элемент будет (+)- комбинацией первых элементов FIB и хвостовых FIB, которые будут 1-м и 2-м элементом FIB, которые уже помечены как оцененные. Это работает с n-м элементом, подлежащим оценке, и (n-2)-й и (n-1)-ым уже оцененными элементами соответственно.

Вы можете визуализировать это по-разному, а именно:

  fibs!!(i+0)
+ fibs!!(i+1)
= fibs!!(i+2)

            (fibs)
zipWith(+)  (tail fibs)
        =   (drop 2 fibs)

          1 : 1 : 2 : 3 ...
     (1 :)1 : 2 : 3 : 5 ...
 (1 : 1 :)2 : 3 : 5 : 8 ...

---

2.) Ваш пример "sieve (p:ps) xs"

primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]  
                                    -- or:  filter ((/=0).(`rem`p)) t
                      where (h,~(_:t)) = span (< p*p) xs

В "решето (p: ps) хз",

• оценивается,
• ps не оценен, и
• xs - это оцененный бесконечно частичный список (не содержащий p, но содержащий p²), который можно угадать, прочитав рекурсию и / или признав, что значения h должны быть простыми.

Sieve должна возвращать список простых чисел после p, так что, по крайней мере, следующее простое число должно быть оценено.

• Следующее простое число будет в списке h, который является списком всех (уже просеянных) чисел k, где p
• t содержит все числа xs выше p². t следует оценивать как ленивый, а не как можно скорее, потому что может даже не быть необходимости оценивать все элементы в h. (Только первый элемент h должен быть оценен.)

Остальная часть определения функции - это рекурсия, где следующий xs равен t со всеми n*p, просеянными.

---

В случае foldr, анализ покажет, что "go" определяется только для ускорения времени выполнения, а не для удобства чтения. Вот альтернативное определение, которое легче проанализировать:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (.:) e (x:xs) = x .: (foldr (.:) e xs)
foldr (.:) e []     = e

Я описал его функциональность здесь (без анализа).

Чтобы обучить анализу такого типа, вы можете прочитать источники некоторых стандартных библиотек; то есть scanl, scanr, unfoldr в источнике Data.List.