如果我来自命令式编程背景，如何理解Haskell中没有动态变量来跟踪事物的概念？

Question

所以我正在学习Haskell。我目前正在阅读Learn You a Haskell for Great Good的第11章，并在做99 Haskell Problems以及Project Euler Problems。

目前进展还算顺利，但每当我需要跟踪“变量”时，我发现自己总是会做同样的事情。我只需创建另一个函数来作为参数接收这些“变量”，并根据情况递归地传入不同的值。以下是我解决Project Euler中问题7的方案，其要求是找到第10001个素数：

answer :: Integer
answer = nthPrime 10001

nthPrime :: Integer -> Integer
nthPrime n
  | n < 1 = -1
  | otherwise = nthPrime' n 1 2 []


nthPrime' :: Integer -> Integer -> Integer -> [Integer] -> Integer
nthPrime' n currentIndex possiblePrime previousPrimes
  | isFactorOfAnyInThisList possiblePrime previousPrimes = nthPrime' n currentIndex theNextPossiblePrime previousPrimes
  | otherwise = 
    if currentIndex == n 
      then possiblePrime 
      else nthPrime' n currentIndexPlusOne theNextPossiblePrime previousPrimesPlusCurrentPrime
        where currentIndexPlusOne = currentIndex + 1
              theNextPossiblePrime = nextPossiblePrime possiblePrime
              previousPrimesPlusCurrentPrime = possiblePrime : previousPrimes

我认为你会明白的。让我们忽略这个解决方案可以更有效的事实，我已经意识到了。

所以我的问题有两个部分。首先，我是否在错误地学习Haskell？我是否被命令式编程思维束缚，没有像应该一样接受Haskell？如果是这样，我该如何避免这种情况？你能给我推荐一本书或来源，帮助我更像Haskell地思考吗？

非常感谢您的帮助,

-Asaf

- Asaf

---

希望您能够理解“懒惰”对解决问题的帮助很大。例如，对于这个问题，我创建了一个无限长的质数列表，并在其中进行索引以获取第10001个元素。 - Lily Ballard

但是，如果您的意思是您使用筛法创建该列表，那么这将如何工作？ 因为筛法不是通过遍历整个列表来删除其余部分的倍数吗？ - Asaf

@KevinBallard 对不起，我有点困惑。我想象中的筛法是，你从一个列表[2..]开始，也就是从2到无穷大，然后遍历这个列表，删除所有2的倍数。当你完成删除所有2的倍数（你永远也做不完）之后，你去找下一个剩下的数字3，并删除所有3的倍数。我感觉你在暗示其他事情，更接近于我的函数工作方式，但是无限列表在哪里发挥作用呢？ - Asaf

@llayland，说得好，但是如果您不考虑计算所需的“步骤”，如何考虑程序的效率呢？特别是在像这样的问题中，如果您提供的解决方案过于简单，您的计算机将需要很长时间才能为您提供答案。 - Asaf

@Asaf: 类似于 primes = 2 : 3 : filter isPrime [5,7..] where isPrime n = not $ any ((==0) . mod n) $ takeWhile ((<n) . (^2)) primes 这样的东西 - Lily Ballard

Answer 1

我是否被命令式编程思维束缚，没有像应该一样拥抱Haskell？

你并没有被束缚，至少我不希望如此。你所经历的是非常正常的。在使用命令式语言时，您学会了（也许是不知不觉地）从一个非常特定的角度看待编程问题 - 即用冯诺伊曼机器的术语来描述。

例如，如果您要创建一个包含某些数字序列的列表（假设我们想要前1000个偶数），则您会立即想到：使用链表实现（可能来自您的编程语言的标准库），循环和一个变量，您将设置起始值，然后循环一段时间，通过加2更新变量并将其放置于列表末尾。

注意到您大多考虑如何服务机器？内存位置、循环等！在命令式编程中，人们始终考虑如何按特定顺序操作某些内存单元以达到解决方案。（这也是初学者发现学习（命令式）编程困难的原因之一。非程序员根本不习惯通过将问题简化为一系列内存操作来解决问题。他们为什么要这样做呢？但是一旦您学会了，您就可以掌握命令式世界的力量。对于函数式编程，您需要放弃这种思维方式。）

在函数式编程中，特别是在Haskell中，您仅声明列表的构建法则。因为列表是一个递归数据结构，所以这个法则当然也是递归的。在我们的例子中，例如，我们可以说以下内容：

constructStartingWith n = n : constructStartingWith (n+2)

差不多完成了！要得到我们的最终列表，我们只需要说明从哪里开始，以及需要多少个：

result = take 1000 (constructStartingWith 0)

请注意，库中还提供了一个更通用版本的constructStartingWith，称为iterate，它不仅需要起始值，还需要将当前值转换为下一个列表元素的函数：

iterate f n = n : iterate f (f n)
constructStartingWith = iterate (2+)   -- defined in terms of iterate

另一种方法是假设我们有另一个列表，我们可以很容易地从中制作出我们的列表。例如，如果我们有前n个整数的列表，我们可以通过将每个元素乘以2轻松地将其变成偶数列表。现在，在Haskell中，前1000个（非负）整数的列表简单地表示为：

[0..999]

有一个函数map，它通过将给定的函数应用于每个参数来转换列表。 我们想要的功能是使元素加倍：

double n = 2*n

因此：

result = map double [0..999]

以后你将学习更多的快捷方式。例如，我们不需要定义double，而可以使用一个部分：(2*)或者我们可以直接将列表写成序列[0,2..1998]。

但是现在还不知道这些技巧不应该让你感到难过！你现在面临的主要挑战是培养一种心态，即你需要看到构建前1000个偶数列表的问题是一个两阶段的问题：a）定义所有偶数的列表长什么样子； b）从该列表中取出一定的部分。一旦你开始这样思考，即使你仍然使用手写版本的iterate和take，你也完成了任务。

回到欧拉问题：这里我们可以使用自顶向下的方法（以及一些基本的列表操作函数，人们确实应该了解：head、drop、filter、any）。首先，如果我们已经有了素数列表，我们可以只删除前1000个并取剩余部分的头部来获得第1001个素数：

result = head (drop 1000 primes)

我们知道从一个无限列表中删除任意数量的元素后，仍将保留一个非空列表可供选择 head，因此，在这里使用head是合理的。当你不确定是否有超过1000个质数时，应该编写类似以下内容的代码：

result = case drop 1000 primes of
    [] -> error "The ancient greeks were wrong! There are less than 1001 primes!"
    (r:_) -> r

现在来到了难点。不知道如何继续，我们可以编写一些伪代码：

primes = 2 : {-an infinite list of numbers that are prime-}

我们已经确定了2是第一个质数，也就是所谓的基本情况，因此我们可以把它写下来。未填充的部分让我们有些思考。例如，列表应该从大于2的某个值开始，这是显而易见的原因。因此，修正：

primes = 2 : {- something like [3..] but only the ones that are prime -}

现在，出现了一个模式，需要学习认识。这肯定是通过一个谓词（即素性）filter的列表（我们还不知道如何检查素数，但逻辑结构是重要的点。(而且，我们可以确定测试素数是可能的！)）。这让我们能够编写更多代码：

primes = 2 : filter isPrime [3..]

看到了吗？我们已经接近完成了。通过3个步骤，我们已经将一个相当复杂的问题简化为只需要编写一个非常简单的谓词。 同样，我们可以用伪代码来表示：

isPrime n = {- false if any number in 2..n-1 divides n, otherwise true -}

并且可以进一步完善。因为这几乎已经是Haskell，所以太容易了：

isPrime n = not (any (divides n) [2..n-1])
divides n p = n `rem` p == 0

请注意，我们还没有进行优化。例如，我们可以立即构造要过滤的列表，只包含奇数，因为我们知道偶数不是质数。更重要的是，我们希望减少在isPrime中必须尝试的候选数的数量。这里需要一些数学知识（当然，如果您用C++或Java编写此代码也是如此），告诉我们只需检查我们正在测试的n是否被任何质数整除，而且我们不需要检查平方大于n的质数的可除性。幸运的是，我们已经定义了质数列表，并且可以从中选择候选集！我把这留作练习。

稍后您将学习如何使用标准库和语法糖，例如部分、列表推导式等，并逐渐放弃编写自己的基本函数。

甚至稍后，当您再次使用命令式编程语言时，您将发现没有无限列表、高阶函数、不可变数据等非常难以生存。这将像从C转回Assembler一样困难。

祝玩得开心！

- Ingo

---

谢谢你提供这样一个深思熟虑的帖子。当我遇到困难时，我一定会尝试模仿那种思维结构。我希望有一天我也能像你一样“发现很难离开……”。我决定学习Haskell来成为更好的程序员，因为显然它会迫使我用全新的方式思考。挑战可能是最令人愉快的部分。这就是为什么我没有选择另一种命令式语言，那可能太容易了。 - Asaf

没有解释为什么需要 2 :。它可以被删除而不会使任何东西变得不正确。 - Rotsor

Rotsor：这篇文章已经够长了 :) 但我认为从你熟悉的东西开始是个好主意。例如，我们知道质数是以2开头的列表。也可以写成2:3:5:7: ....就像你说的，在最后并没有什么区别。 - Ingo

另一方面，在优化版本中，我们仅通过从“primes”中选择的质数进行除法运算，因此当 isPrime n = not (any (divides n) (takeWhile (\p -> p*p <= n) primes)) 时，我们需要2存在，即只有在未经优化的版本中才能确定2的质数性。 - Ingo

Answer 2

起初拥有命令式思维方式是可以的。随着时间的推移，您将更加熟悉事物，并开始看到可以创建更具功能性的程序的地方。熟能生巧。

至于使用可变变量进行工作，如果您遵循将变量转换为函数参数和迭代转换为尾递归的经验法则，可以暂时保留它们。

- hugomg

---

这让我感觉好多了。我想我只需继续阅读和实践，并暂时不用过于担心我的代码是否“类似 Haskell”。 - Asaf

Answer 3

我能想到的有:

• Typeclassopedia。该文档的官方v1版本是一个pdf，但作者已将其v2版本转移到了Haskell维基上。

• Monad是什么? 这个SO问答是我能找到的最好的参考资料。

• 什么是Monad Transformer？ Monad Transformers逐步讲解。

• 向大师学习: 阅读和学习Haskell的好代码。

• 更高级的主题，如GADTs。这里有一个视频，非常好地解释了它。

• 最后但并非最不重要的，是#haskell IRC频道。没有任何东西可以比与真正的人交谈更接近。

- edwardw

---

不确定这是否是OP正在寻找的东西。这些都是抽象概念，但并没有真正解决纯粹和懒惰思考的问题。这是一种你必须逐渐习惯的东西，但我认为这是在错误的层面上回答了问题。 - luqui

非常感谢您提供的所有资源。我最终会阅读它们（并观看/聊天）。您的答案确实回答了我的最后一个问题，但没有回答之前的问题。话虽如此，我很抱歉必须在您的答案和其他答案之间做出选择。 - Asaf

Answer 4

我认为从您的代码到更像Haskell的代码的重大变化在于更好地使用高阶函数、模式匹配和惰性求值。例如，您可以像这样编写nthPrime函数（再次忽略效率，使用类似于您之前使用的算法）：

nthPrime n = primes !! (n - 1) where
  primes = filter isPrime [2..]
  isPrime p = isPrime' p [2..p - 1]
  isPrime' p [] = True
  isPrime' p (x:xs) 
    | (p `mod` x == 0) = False
    | otherwise = isPrime' p xs

例如，nthPrime 4 返回 7。请注意以下几点：

• isPrime' 函数使用模式匹配来实现函数，而不是依赖于if语句。
• primes 值是所有质数的无限列表。由于Haskell是惰性的，因此这是完全可以接受的。
• 使用 filter 而不是使用递归重新实现该行为。

随着经验的增加，您会发现自己编写更具惯用性的Haskell代码 - 这在经验上自然而然地发生。因此，请不要担心，只需继续练习并阅读其他人的代码。

- David Miani

---

使用更高阶函数：isPrime p = all ((/= 0) . mod p) [2..p-1] - hammar

我同意你的观点，我认为解决方案可能是尝试始终使用Hoogle，并与其他人的解决方案进行比较，以便更熟悉高阶函数。目前，其中许多函数对我来说似乎很奇怪。我发现我几乎从不使用map / all，虽然我使用$符号来避免括号，但我在使用无参函数风格（利用“.”符号）时遇到了很多麻烦。 - Asaf

Answer 5

另一种方法，只是为了多样性！强烈使用懒惰...

module Main where

nonmults :: Int -> Int -> [Int] -> [Int]
nonmults n next [] = []
nonmults n next l@(x:xs)
   | x < next = x : nonmults n next xs
   | x == next = nonmults n (next + n) xs
   | otherwise = nonmults n (next + n) l

select_primes :: [Int] -> [Int]
select_primes [] = []
select_primes (x:xs) = 
  x : (select_primes $ nonmults x (x + x) xs)

main :: IO ()
main = do
  let primes = select_primes [2 ..]
  putStrLn $ show $ primes !! 10000 -- the first prime is index 0 ...

- DanK

Answer 6

我希望能够不使用任何函数式编程或数学来回答你的问题，这并不是因为我认为你理解不了，而是因为你的问题非常普遍，也许其他人可以从我试图描述的思维方式中受益。我想先说明一下，尽管我并不是Haskell方面的专家，但我已经通过意识到以下几点克服了你所描述的心理障碍：

1. Haskell很简单

Haskell以及其他我不太熟悉的函数式语言与C、Java、Python等“常规”语言确实有很大不同。不幸的是，由于我们的心理机制，人类过早地得出结论，即如果某个东西不同，那么A）他们不理解它，B）它比他们已经知道的更复杂。如果我们客观地看待Haskell，我们会发现这两个推断是完全错误的：

"但我不理解它 :( "

实际上，你需要。Haskell和其他函数式语言中的所有内容都是基于逻辑和模式定义的。如果你能回答一个简单的问题，比如“如果所有Meeps都是Moops，而所有Moops都是Moors，那么所有Meeps都是Moors吗？”，那么你可能可以自己编写Haskell预处理程序。为了进一步支持这一观点，请考虑Haskell列表是用Haskell术语定义的，并不是特殊的巫术。

“但它很复杂”

实际上恰恰相反。它的简洁性是如此裸露无遮挡，以至于我们的大脑一开始就难以理解它。与其他语言相比，Haskell实际上具有更少的“功能”和更少的语法。当你阅读Haskell代码时，你会注意到几乎所有的函数定义在风格上看起来都是一样的。这与Java完全不同，Java有像类、接口、for循环、try/catch块、匿名函数等结构，每个结构都有自己的语法和惯用语。

你提到了 $ 和 .，记住它们像任何其他的 Haskell 函数一样被定义，不一定需要使用。然而，如果没有这些函数可用，随着时间的推移，当你注意到它们有多方便时，你可能会自己实现这些函数。

2. 没有任何东西的 Haskell 版本 这实际上是一件非常好的事情，因为在 Haskell 中，我们有自由来精确地定义事物。大多数其他语言提供构建块，人们将它们串联成程序。Haskell 先让你定义一个构建块，然后再用它来构建。

许多初学者会问类似“如何在Haskell中使用for循环”的问题，而那些试图帮助他们的人可能会给出一个不幸的答案，其中可能涉及辅助函数、额外的Int参数和尾递归直到达到0。当然，这种结构可以计算类似于for循环的东西，但绝不是for循环，也不是for循环的替代品，如果考虑执行流程，它甚至不能算是与for循环相似。类似的是用于模拟状态的State monad。它可以用来完成其他语言中静态变量所做的类似事情，但绝不是同一件事情。当人们回答这些问题时，大多数人都省略了最后一个关键点，即它与原本的东西并不相同，我认为这只会更加困惑人们，直到他们自己意识到这一点。

3. Haskell是一个逻辑引擎，而不是编程语言。

这可能是我试图表达的最不确切的观点，但请听我解释。在命令式编程语言中，我们关心让机器执行任务、执行操作、改变状态等等。在Haskell中，我们尝试定义事物是什么，以及它们应该如何行动。通常我们不关心某个东西在任何特定时间正在做什么。这当然有利有弊，但事实就是如此。这与大多数人所想的“编程语言”非常不同。

因此，这是我的看法，如何摆脱命令式思维方式，转向更加函数式的思维方式。认识到Haskell的合理性将帮助您不再奇怪地看待自己的代码。希望以这些方式思考Haskell将有助于您成为更有生产力的Haskeller。

- parker.sikand