递归 Haskell 函数似乎不会终止

为了提高我的 Haskell 技能，我正在尝试解决2018 年代码的到来 https://adventofcode.com/。正如预期的那样，我已经陷入了第一天，特别是第二部分：

- - 第二部分 - -

您注意到设备重复相同的频率更改列表 以及结束。

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

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

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

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

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

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

（此时，设备从列表的开头继续。）

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

当前频率4，变化-2；产生的频率 2，其中有 已经被看见了。

在此示例中，第一个达到两次的频率是2。注意 您的设备可能需要多次重复其频率更改列表 发现重复频率之前的次数，并且重复可能 在处理列表的过程中可以找到。

以下是其他示例：

+1、-1 首先达到 0 两次。

+3、+3、+4、-2、-4 首先达到 10 两次。

-6、+3、+8、+5、-6 首先达到 5 两次。

+7、+7、-2、-7、-4 首先两次达到 14。

您的设备第一次达到两次的频率是多少？

基本上，我有一个非常大的清单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 https://adventofcode.com/2018/day/1/input.

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

这是一个想法，

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

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

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

if 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

Note find返回一个Maybe (Int, Set Int)。它可能会发现Nothing或返回Just (x,s)对于某些频率x那已经在s。我们用fmap fst转动Just (x,s) into Just x.

EDIT

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

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

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符号，以及不让它计算前两个列表的压缩。我不太确定“融合”两个列表的构建是否值得。可读性有点差。使用三种函数，一种用于频率，一种用于集合，一种用于压缩，可能是最好的。