Haskell小型函数实现

Question

我一直在尝试使用迭代和takeWhile函数来实现这个函数的小型实现。它不一定要使用这些函数，我只是想把它变成一行代码。我可以看出其中的模式，但似乎无法利用它，除非基本上做相同的代码，只是用迭代代替递归。

fun2 :: Integer -> Integer
fun2 1 = 0
fun2 n 
    | even n = n + fun2 (n `div` 2)
    | otherwise = fun2 (3 * n + 1)

任何帮助都将非常感激。我已经为此苦苦挣扎了数小时。谢谢。

- xZel

---

你的四行版本有什么问题吗？我认为它非常清晰，比任何一行版本都更易读。 - tom

这只是Haskell课程的一个挑战。我花了很多时间在上面，真的只想要一些建议。我有一个稍微简化的版本。 - xZel

Answer 1

如果您想使用iterate完成此操作，关键是将其分解为更小的逻辑部分：

• 使用规则生成序列

  a_k+1 = a_k/2（如果a_k是偶数）

  a_k+1 = 3a_k+1（如果a_k是奇数）

• 在a_j = 1处停止序列（如果Collatz猜想成立，则所有序列都会停止）。

• 过滤路径上的偶数元素
• 对它们求和

因此，这就变成了：

  f = sum . filter even . takeWhile (>1) . iterate (\n -> if even n then n `div` 2 else 3*n + 1)

然而，我认为使用帮助函数会更清晰。

  f = sum . filter even . takeWhile (>1) . iterate collatz
    where collatz n | even n    = n `div` 2
                    | otherwise = 3*n + 1

这可能不会省掉你的代码行数，但将你的递归转化为数据生成。

- rampion

---

是的，你的if语句行就是我所思考的，但我无法想出如何实现。辅助函数也非常棒。谢谢，伙计。 - xZel

Answer 2

首先，我同意Tom的评论，你的四行代码没有任何问题。它很易读。然而，将Haskell函数转化为单行代码有时是一项有趣的练习。谁知道呢，你可能会学到些什么！

目前你有：

fun 1 = 0
fun n | even n    = n + fun (n `div` 2)
      | otherwise = fun (3 * n + 1)

您可以始终使用 guards 将表达式转换为 if

fun 1 = 0
fun n = if even n then n + fun (n `div` 2) else fun (3 * n + 1)

您可以将一系列模式匹配转换为 case 表达式：

fun n = case n of
            1 -> 0
            _ -> if even n then n + fun (n `div` 2) else fun (3 * n + 1)

最后，您可以将一个表达式转换为一系列if（实际上，通常情况下，这需要一个函数参数的EQ实例，但是由于您正在使用Integer，所以这无关紧要）。

fun n = if n == 1 then 0 else if even n then n + fun (n `div` 2) else fun (3 * n + 1)

我想你会同意这比起最初的内容难以阅读得多。

- Chris Taylor

Answer 3

一行代码 ;)

fun2 n = if n==1 then 0 else if even n then n + fun2 (n `div` 2) else fun2 (3 * n + 1)

我的感觉是，除了查找表之外，这个函数无法在没有递归的情况下实现，因为传递给递归的参数似乎是不可预测的（除了 n 作为 2 的幂次方）。

另一方面，rampion 帮助我学到了新东西。

- גלעד ברקן