迭代函数并分析haskell中的结果 [英] Iterating a function and analysing the result in haskell
问题描述
好的,回顾我的上一个问题我仍在努力学习haskell并解决当前从以下迭代中找到最长链的问题:
chain n | n == 0 =错误你在说什么?
| n == 1 = [1]
| rem n 2 == 0 = n:chain(n`div` 2)
|否则= n:链(3 * n + 1)
我已经排序了,但我需要从一个低于1,000,000的起始数字找到最长的链。那么,如何让每个起始数字达到1,000,000,然后打印链长最长的数字。
我可以这样做:
Main>长度(链n)
我假设我需要输出作为数组,然后使用最大值
函数来查找值的最大链长,然后查看它在答案数组中的距离。
这是寻找解决方案的好方法或者是否有更好的方法(可能效率更高)? 解决方案
关于最大值
部分。要得到 list (这就是Haskell的[],数组是不同的结构),你需要使用 map
高阶函数,就像这个:
chainLength n =长度(链n)
长=地图chainLength [1 .. 1000000]
基本上, map
一个函数和一个列表。它将函数应用于列表中的每个元素,并返回结果列表。
由于您需要链的长度的数字,您可能需要更改 chainLength
函数也可以返回数字,如下所示:
chainLength n =(n,length(chain n))
这样你就可以得到一组数组,每个数字及其链长。
现在您需要获得具有最大第二个分量的组合。这就是 maximumBy
函数的作用。它的工作方式与最大值
类似,但是它将函数作为参数来选择如何比较值。在这种情况下,这一对的第二个组成部分。该比较函数使用两个数字并返回类型 Ordering
的值。这种类型只有三种可能的值: LT
, EQ
, GT
,分别小于,等于和大于。
因此,我们需要一个函数,给定两个对告诉我们第二个组件如何相互比较:
compareSnd(_,y1)(_,y2)=比较y1 y2
- 或者,如果您导入Data.Function,你可以这样写(谢谢alexey_r):
compareSnd = compare`on` snd - 很好地读取
我使用了比较数字的默认比较
函数(以及不仅仅是数字)。
longestChain = maximumBy compareSnd长度
现在我们只需要使用这个函数获得最大值: code>
这会为您带来一对最长链条和相关的数字积水长度。请随意申请 fst
和 snd
。
<请注意,这可以更简洁地使用 zip
和构图,但由于您将问题标记为新手,我认为最好这样分解。 / p>
Ok, referring back to my previous question, I am still working on learning haskell and solving the current problem of finding the longest chain from the following iteration:
chain n | n == 0 = error "What are you on about?"
| n == 1 = [1]
| rem n 2 == 0 = n : chain (n `div` 2)
| otherwise = n : chain (3 * n + 1)
I have this bit sorted, but I need to find the longest chain from a starting number below 1,000,000. So how do I make it do each starting number up to 1,000,000 and then print the one with the longest chain length. I can do it for one example with:
Main> length (chain n)
I assume I need the output as an array and then use the maximum
function to find the value largest chain length and then see how far along it is in the array of answers.
Is this a good way to go about finding a solution or is there a better way (perhaps with better efficiency)?
You are right about the maximum
part. To get the list (that's what Haskell's []s are, arrays are different structures) you need to use the map
higher-order function, like this:
chainLength n = length (chain n)
lengths = map chainLength [1..1000000]
Essentially, map
takes as arguments a function and a list. It applies the function to each element in the list and returns the list of the results.
Since you will be needing the number whose chain has that length, you may want change the chainLength
function to return the number as well, like this:
chainLength n = (n, length (chain n))
That way you will have an array of pairs, with each number and its chain length.
Now you need to get the pair with the largest second component. That's where the maximumBy
function comes in. It works just like maximum
but takes a function as a parameter to select how to compare the values. In this case, the second component of the pair. This comparison function takes two numbers and returns a value of type Ordering
. This type has only three possible values: LT
, EQ
, GT
, for less than, equal, and greater than, respectively.
So, we need a function that given two pairs tells us how the second components compare to each other:
compareSnd (_, y1) (_, y2) = compare y1 y2
-- Or, if you import Data.Function, you can write it like this (thanks alexey_r):
compareSnd = compare `on` snd -- reads nicely
I used the default compare
function that compares numbers (well, not just numbers).
Now we only need to get the maximum using this function:
longestChain = maximumBy compareSnd lengths
That gets you a pair of the number with the longest chain and the corresponding length. Feel free to apply fst
and snd
as you please.
Note that this could be more much more concisely using zip
and composition, but since you tagged the question as newbie, I thought it better to break it down like this.
这篇关于迭代函数并分析haskell中的结果的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!