haskell - 递归 Haskell 函数似乎不会终止

Question

为了提高我的 Haskell 技能，我正在尝试解决 Advent of Code 2018 。正如预期的那样，我已经陷入了第一天的困境，特别是第二部分:

--- 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:

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

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

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

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

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

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

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

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.

Here are other examples:

+1, -1 first reaches 0 twice.

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

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

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

What is the first frequency your device reaches twice?

基本上，我有一个非常大的列表vals::[Int]，其中包括上面提到的所有频率变化。

这是我为解决这个问题而编写的函数:

-- [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 中的描述中提供的值测试此函数:

*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> 

所有结果都是正确的，所以我假设我的函数工作正常。现在的问题是，当我将其编译成一个从文件读取输入列表的程序时，该程序永远不会终止。代码如下:

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 构建，但正如我所说，永远不会终止并且不打印任何结果。我缺少什么？输入文件可以找到here 。

Answer 1

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

这是一个想法，

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

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

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

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

这可能看起来效率极低，但由于 Haskell 很懒，这些列表将根据需要生成。

我们需要导入模块来处理集合和也许，

import Data.Set
import Data.Maybe

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

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

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

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

一旦我们有了频率和集合，我们就差不多完成了。main 函数只是将所有内容放在一起。它组合两个列表并找到第一对 (fi , {f0,...,fi-1}) 使得 fi ∈ {f0,...,fi-1}，并返回对应的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)。对于s 中已经存在的某个频率x，它可能找不到Nothing 或返回Just (x,s)。我们使用 fmap fst 将 Just (x,s) 转换为 Just x。

---

编辑

一旦你的工作顺利进行，如果你愿意的话，可以优化一些东西，或者尝试一下你的风格。以下是一个更简洁、可能更有效的版本。

频率和集合的列表可以一次性构建在一起。

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

这样它就可以用于结果函数了。此外，我们还可以利用 Maybe 作为 monad 的优势来使内容更具可读性。

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

这就是一个相当简短的解决方案。我喜欢结果函数的变化。我喜欢 do 表示法，并且不让它计算前两个列表的压缩。我不太确定“融合”两个列表的构建是否值得。可读性有点差。使用三种函数，一种用于频率，一种用于集合，一种用于压缩，可能是最好的。