递归Haskell函数似乎没有终止 [英] Recursive Haskell function seemingly doesn't terminate

问题描述

为了提高我的Haskell技能，我正在尝试解决代码2018的出现.不出所料，我已经停留在第1天，尤其是第2部分:

To improve my Haskell skills, I'm trying to solve the Advent of Code 2018. As expected, I am already stuck on day 1, specifically on part 2:

-第二部分---

--- Part Two ---

您注意到设备重复了相同的频率更改列表 及以上.

You notice that the device repeats the same frequency change list over and over.

要校准设备，您需要找到它的第一个频率 到达两次.

To calibrate the device, you need to find the first frequency it reaches twice.

例如，使用上面相同的更改列表，设备将 循环如下:

For example, using the same list of changes above, the device would loop as follows:

当前频率0，变化+1；结果频率1.

Current frequency 0, change of +1; resulting frequency 1.

当前频率1，变化为-2；结果频率为-1.

Current frequency 1, change of -2; resulting frequency -1.

当前频率-1，变化+3；结果频率2.

Current frequency -1, change of +3; resulting frequency 2.

当前频率2，变化+1；结果频率3.

Current frequency 2, change of +1; resulting frequency 3.

(此时，设备将从列表的开头继续.)

(At this point, the device continues from the start of the list.)

当前频率3，变化+1；结果频率4.

Current frequency 3, change of +1; resulting frequency 4.

当前频率4，变化为-2；产生的频率2 已经被看到.

Current frequency 4, change of -2; resulting frequency 2, which has already been seen.

在此示例中，达到两次的第一个频率为2.注意 您的设备可能需要重复其频率变化列表，其中许多 找到重复频率之前的时间，并且可能重复 可以在处理列表的中间找到.

In this example, the first frequency reached twice is 2. Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.

还有其他示例:

+ 1，-1首先到达0两次.

+1, -1 first reaches 0 twice.

+ 3，+ 3，+ 4，-2，-4首先达到10两次.

+3, +3, +4, -2, -4 first reaches 10 twice.

-6，+ 3，+ 8，+ 5，-6首先达到5两次.

-6, +3, +8, +5, -6 first reaches 5 twice.

+ 7，+ 7，-2，-7，-4首先到达14.

+7, +7, -2, -7, -4 first reaches 14 twice.

您的设备达到两次的第一个频率是什么?

What is the first frequency your device reaches twice?

基本上，我有一个很大的列表vals::[Int]，其中包括上述所有频率变化.

Basically, I have a very large list vals::[Int] that includes all the frequency changes mentioned above.

这是我为解决此问题而编写的功能:

Here is the function I wrote for solving this problem:

-- [1] The list of frequency changes
-- [2] The first repeat frequency
--             [1]      [2]
part2helper :: [Int] -> Int
part2helper ds = go ds []
    where go ds [] = go ds [0]
          go (d:ds) [f] = go ds $ (f+d):[f]
          go (d:ds) (f:fs) =
              if f `elem` fs then f
              else go ds $ (d+f):f:fs

我使用ghci中的描述中提供的值测试此功能:

I test this function with the values provided in the description in ghci:

*Main> part2helper (cycle [1, -2, 3, 1])
2
*Main> part2helper (cycle [1, -1])
0
*Main> part2helper (cycle [3, 3, 4, -2, -4])
10
*Main> part2helper (cycle [7, 7, -2, -7, -4])
14
*Main> 

所有结果都是正确的，因此我认为我的函数可以正常工作.现在的问题是，当我将其编译为从文件读取输入列表的程序时，该程序永远不会终止.这是代码:

All result are correct, so I assume my function works correctly. The problem now is, when I compile this into a program that reads the input list from a file, the program never terminates. Here's the code:

module Main where

import System.Environment

main = do 
    [input] <- getArgs
    s       <- readFile input
    let n    = lines $ s
        vals = map (read::String->Int) $ fmap (filter (/='+')) n
        sol  = part2helper (cycle vals)
    print sol

-- [1] The list of frequency changes
-- [2] The first repeat frequency
--             [1]      [2]
part2helper :: [Int] -> Int
part2helper ds = go ds []
    where go ds     []     = go ds [0]
          go (d:ds) [f]    = go ds $ (f+d):[f]
          go (d:ds) (f:fs) =
              if f `elem` fs then f
              else go ds $ (d+f):f:fs

这将正确构建GHC，但正如我所说，永远不会终止并且不会显示任何结果.我想念什么?可以在此处找到输入文件.

This builds with GHC correctly, but as I said, never terminates and prints no result. What am I missing? The input file can be found here.

推荐答案

您正在尝试将所有内容放到一个函数中.如果您以模块化的方式工作，将问题分解成更小的问题，那就更好了.

You're trying to put everything together in a single function. It's much better if you work in a modular fashion, breaking the problem into smaller ones.

这是个主意，

• 生成频率序列，
  f0, f1, f2...
• 生成频率累积集的序列
  {}, {f0}, {f0,f1}, {f0,f1,f2}...
• 检查重复插入的内容，即
  fi这样的fi ∈ {f0..fi-1}

• generate the sequence of frequencies,
  f0, f1, f2...
• generate the sequence of cumulative sets of frequencies
  {}, {f0}, {f0,f1}, {f0,f1,f2}...
• check repeated insertions, i.e.
  fi such that fi ∈ {f0..fi-1}

为了使最后一点更清楚，请考虑

To make things clearer regarding the last point consider,

 f0, f1,   f2,      f3...
 {}, {f0}, {f0,f1}, {f0,f1,f2}...`

如果f3是重复，则f3 ∈ {f0,f1,f2}

这似乎效率很低，但是由于Haskell懒惰，因此将根据需要生成这些列表.

This may seem terribly inefficient but because Haskell is lazy, these lists will be generated as needed.

我们需要导入模块以使用集合和也许，

We'll need to import modules to work with sets and maybes,

import Data.Set
import Data.Maybe

可以通过scanl (+)从第一个频率生成频率并列出频率变化列表.函数scanl (+) x xs从x开始，使用运算符+操作xs的元素，从而生成总和列表.

Generating the frequencies from the first frequency and a list of frequency changes can be done via scanl (+). The function scanl (+) x xs operates the elements of xs with the operator + , starting at x, generating the cumulative list of sums.

freqs :: Int -> [Int] -> [Int]
freqs = scanl (+)  

现在我们可以生成集合列表.在这里，我们也使用scanl.在每个步骤中，我们都会插入一个新的频率，然后从空集开始.

Now we can generate the list of sets. Here too we use a scanl. In each step we insert a new frequency, and we start with the empty set.

sets  :: [Int] -> [Set Int]
sets  = scanl (\s x -> insert x s) (empty) 

一旦我们有了频率和集合，我们就完成了大部分工作.main函数将所有内容放在一起.它组合两个列表，并找到第一对(fi , {f0,...,fi-1})，例如fi ∈ {f0,...,fi-1}，并返回相应的fi

Once we have the frequencies and the sets we are pretty much done.The main function just puts everything together. It combines both lists and finds the first pair (fi , {f0,...,fi-1}) such that fi ∈ {f0,...,fi-1}, and returns the corresponding fi

result :: Int -> [Int] -> Maybe Int
result x xs = let fs = freqs x xs
                  ss = sets fs                  
                  r  = find (\(y,s) -> y `elem` s) (zip fs ss)
              in fmap fst r

注意find返回Maybe (Int, Set Int).它可能会找到Nothing或为s中已经存在的某个频率x返回Just (x,s).我们使用fmap fst将Just (x,s)转换为Just x.

Note find returns a Maybe (Int, Set Int). It may find Nothing or return Just (x,s) for some frequency x that was already in s. We use fmap fst to turn Just (x,s) into Just x.

编辑

一旦您愿意的话，可以优化一些东西，或者尝试自己的风格.以下是更简洁的版本，可能是更有效的版本.

Once you've got things working if you wish to, may optimize a few things, or play around with your style. The following is a more succinct, and possibly a little bit more efficient version.

可以一次性建立频率和频率列表.

The list of frequencies and sets can be built together in one go.

freqsets :: Int -> [Int] -> [(Int, Set Int)]
freqsets f0 = scanl (\(f,s) x -> (f+x,insert f s)) (f0,empty) 

因此可以随时将其用于result函数.同样，我们可以利用Maybe作为monad的优势使事情更具可读性.

And so it's ready to use for the result function. Also we can take advantage of Maybe being a monad to make things a bit more readable.

result :: Int -> [Int] -> Maybe Int
result f0 xs = do (f,_) <- find(\(y,s)->y `elem` s) (freqsets f0 xs)
                  return f 

就在那里，这是一个相当短的解决方案.我喜欢结果函数中的更改.我喜欢do表示法，也没有让它计算前两个列表的压缩率.我不确定将两个列表的构建融合"是否值得.可读性较差.最好使用三种功能，一种用于频率，一种用于组，另一种用于拉链.

And there you have it, a rather short solution. I like the change in the result function. I like the do notation, as well as not having it calculate the zipping of the two previous lists. I'm not so sure if "fusing" the building of both lists is worth it. It's a bit less readable. Using three functions, one for frequencies, one for sets, and one for zipping, might be best.

这篇关于递归Haskell函数似乎没有终止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！