13

所以我正在尝试自学 Haskell。我目前正在学习 Haskell for Great Good的第 11 章，并且正在做99 个 Haskell 问题以及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 的想法？

非常感谢您的帮助，

-阿萨夫

4

6 回答 6

14

我是否停留在命令式编程思维中，没有像我应该的那样拥抱 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，但可以使用一个 section:(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 回到汇编程序一样困难。

玩得开心！

于 2011-12-09T11:44:35.570 回答
12

一开始有必要的心态是可以的。随着时间的推移，您会越来越习惯事物并开始看到可以拥有更多功能程序的地方。熟能生巧。

至于使用可变变量，如果您遵循将变量转换为函数参数并迭代为尾递归的经验法则，您现在可以保留它们。

于 2011-12-09T02:08:45.310 回答
4

在我的头顶上：

于 2011-12-09T02:03:10.003 回答
3

我认为从你的代码到更类似于 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 代码——它会随着经验自动发生。所以不用担心，继续练习，阅读其他人的代码。

于 2011-12-09T06:14:57.653 回答
2

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

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 ...
于 2011-12-10T05:26:39.890 回答
1

我想尝试在不使用任何函数式编程或数学的情况下回答您的问题，不是因为我认为您不会理解它，而是因为您的问题很常见，也许其他人会从我将尝试描述的心态中受益。我首先要说我无论如何都不是 Haskell专家，但是通过意识到以下几点，我已经克服了您所描述的心理障碍：

1. Haskell 很简单

Haskell 和其他我不太熟悉的函数式语言肯定与你的“普通”语言非常不同，如 C、Java、Python 等。不幸的是，我们的心理运作方式，人类过早地得出结论，如果有什么是不同，那么 A）他们不理解它，并且 B）它比他们已经知道的更复杂。如果我们非常客观地看待 Haskell，我们会发现这两个猜想是完全错误的：

“但我不明白 :(”

其实你会的。Haskell 和其他函数式语言中的所有内容都是根据逻辑和模式定义的。如果您可以回答“如果所有 Meeps 都是 Moops，并且所有 Moops 都是 Moors，都是 Meeps Moors？”这样简单的问题，那么您可能可以自己编写 Haskell Prelude。为了进一步支持这一点，请考虑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 将帮助您成为更有效率的 Haskell。

于 2013-12-16T00:53:11.427 回答