如果我来自命令式编程背景,我如何围绕没有动态变量的想法来跟踪Haskell中的事物？

Question

所以我正在努力教自己Haskell.我目前正在第11章" 了解你是一个好的Haskell",我正在做99个Haskell问题以及项目Euler问题.

事情进展顺利,但每当我需要跟踪"变量"时,我发现自己经常做一些事情.我只是创建另一个函数,接受那些"变量"作为参数,并根据情况递归地提供不同的值.举一个例子来说明,这是我对项目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

Answer 1

我是否陷入了强制性的编程思维模式,并没有像我一样接受Haskell？

你没有陷入困境,至少我不希望如此.你经历的是绝对正常的.当你使用命令式语言时,你学习(可能不知道)从非常具体的角度看待编程问题 - 即van Neumann机器.

如果你有一个问题,比如说,制作一个包含一些数字序列的列表(假设我们想要前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个并取其余的头来获得第100个:

result = head (drop 1000 primes)

我们知道在从无限列表中删除任意数量的元素之后,仍然会有一个非空的列表来选择headfrom,因此,在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.幸运的是,我们已经定义了素数列表,可以从那里挑选一组候选人!我把它当作练习.

稍后您将学习如何使用标准库和语法糖,如部分,列表推导等等,您将逐渐放弃编写自己的基本功能.

即使以后,当你必须再次使用命令式编程语言时,你会发现没有infinte列表,更高阶函数,不可变数据等就很难生存.这就像从C转发到Assembler一样困难.

玩得开心!

Answer 2

一开始就有一种强制性的心态是可以的.随着时间的推移,您将更加习惯并开始看到可以拥有更多功能性程序的地方.实践是完美的.

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