Haskell:方程扩展器 1+(1+(1+(1+(…))))=∞

Question

Haskell 是否存在方程扩展器？

像 foldr.com : 1+(1+(1+(1+(…))))=∞
我是 Haskell 的新手，我无法理解为什么某些方程比其他方程更可取。我认为如果我能看到方程的扩展会有所帮助。

例如，我发现 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 on 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 个素数。

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 on Primes

我在手动锻炼和扩展的过程中度过了一段美好的时光。我已经明白它是如何工作的。但是，扩展某些表达式的自动化工具将大大提高我对 Haskell 的理解。

此外，我认为它还可以帮助解决寻求优化 Haskell 代码的问题:

Optimizing Haskell Code

Help optimize my haskell code - Calculate the sum of all the primes below two million

有没有扩展 Haskell 表达式的工具？

Answer 1

David V. 感谢您提供这些链接。 Repr绝对值得添加到我的工具箱中。我想添加一些我发现有用的附加库。

HackageDB : Trace (截至 2010 年 12 月 12 日)

ghc-events 库和程序:用于从 GHC 解析 .eventlog 文件的库和工具

hood 库:通过就地观察进行调试

hpc-strobe 库:Hpc 为正在运行的 Haskell 程序生成的闪光灯

hpc-tracer 程序:带有 AJAX 接口(interface)的 Tracer

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。感谢您提供这些链接。这是个很棒的资源。