Haskell: Equation Expander 1+ (1+ (1+ (1+ (...)))) = ∞

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

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

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

Например, я обнаружил, что foldr vs 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] -->

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

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 на Primes

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

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

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

Ответы

Ответ 1

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

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

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

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

Hood

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). Это напоминает мне Perl CPAN. Спасибо за предоставление этих ссылок. Это отличный ресурс.

Ответ 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))"

Ответ 3

Это ответ на непрошенный вопрос, подумайте об этом как о длинном комментарии.

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

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

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

Два примера:

1.) fibs

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

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

Первые два элемента уже оценены; поэтому отметьте 3-й элемент (который имеет значение 2) как подлежащий оценке, а все остальные - как неоцененные. Третий элемент будет тогда (+) - комбинацией первых элементов fibs и tail fibs, которые будут 1-м и 2-м элементами фиб, которые уже помечены как оцененные. Это работает с n-м элементом, подлежащим оценке, и (n-2) -nd и (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) xs",

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

Сито должно возвращать список простых чисел после p, поэтому по меньшей мере следующее простое вычисляется.

  • Следующее простое число будет в списке h, который является списком всех (уже просеченных) чисел k, где p < k < p²; h содержит только простые числа, потому что xs не содержит ни p, ни любое число, делящееся на любое число ниже 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.