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

关于 Primes 的 Haskell Wiki

我花了很长时间手动进行锻炼和扩展。我开始明白它是如何运作的。然而，扩展某些表达式的自动化工具将极大地提高我对 Haskell 的理解。

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

• 优化 Haskell 代码
• < a href="https://stackoverflow.com/questions/4378194/help-optimize-my-haskell-code-calculate-the-sum-of-all-the-primes-below-two-mil">帮助优化我的haskell代码-计算200万以下所有素数的和

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

Answer 1

大卫·V. 感谢您提供这些链接。 Repr 绝对值得添加到我的工具箱中。我想添加一些我认为有用的额外库。

HackageDB：跟踪 (截至 2010 年 12 月 12 日）

• ghc-events 库和程序：用于从 GHC hood 库解析 .eventlog 文件的库和工具
• ：通过就地观察进行调试
• hpc-strobe 库：Hpc 为正在运行的 Haskell 程序生成的选通脉冲
• hpc-tracer 程序：带有AJAX接口的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
  }

我不知道黑客攻击图书馆（因为我刚刚进入 Haskell）。这让我想起了 Perl 的 CPAN。感谢您提供这些链接。这是一个很好的资源。

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

所有斐波那契数的列表是

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

前两个元素已经被评估；因此，将第三个元素（值为 2）标记为待评估，并将所有剩余元素标记为未评估。第三个元素将是 fibs 的第一个元素和尾部 fibs 的 (+) 组合，这将是 fibs 的第一个和第二个元素，它们已经被标记为已评估。这分别适用于要评估的第 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

在“sieve (p:ps) xs”中，

• p 被评估，
• ps 未被评估， xs
• 是一个评估的无限部分筛选列表（不包含 p 但包含 p²），您可以通过阅读递归来猜测它和/或认识到 h 的值需要是素数。

Sieve 应该返回 p 之后的素数列表，因此至少要评估下一个素数。

• 下一个素数将在列表 h 中，它是所有（已筛选的）数字 k 的列表，其中 p < 。 k＜ p²； h 仅包含素数，因为 xs 既不包含 p 也不包含任何可被 p 以下素数整除的数字。
• t 包含 p² 以上 xs 的所有数字。 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

我已经描述了它的功能 此处（未经分析）。

要训​​练这种类型的分析，您可能需要阅读一些标准库的源代码；即 来源 数据.List.