1

我被分配在 Haskell 中编码一个冰雹序列。必须给我一个整数并创建一个以最后一个数字 1 结尾的整数列表，例如。

-- > hailstone 4
-- [4,2,1]
-- > hailstone 6
-- [6,3,10,5,16,8,4,2,1]
-- > hailstone 7
-- [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

我的答案最后应该只有一个 1，但是一旦达到 1，我不知道如何跳出循环。

hailstone :: Integer -> [Integer]
hailstone = takeWhile (>=1) . (iterate collatz)
  where collatz n = if n == 1
                    then 1
                    else if even n 
                    then n `div` 2 
                    else 3*n+1

最后我得到了无限的 1。我怎样才能解决这个问题？

4

3 回答 3

2

您可以使用包 [hackage]takeUntil :: (a -> Bool) -> [a] -> [a]中的函数。该功能将：utility-ht

取所有元素，直到一个匹配。匹配的元素也被返回。这是与takeWhile (not . p). 它成立takeUntil p xs == fst (breakAfter p xs)。

所以我们可以用它来包括1：

import Data.List.HT(takeUntil)

hailstone :: Integer -> [Integer]
hailstone = takeUntil (== 1) . iterate collatz
  where collatz 1 = 1
        collatz n | even n = div n 2
                  | otherwise = 3 * n + 1

或者我们可以实现takeUntil自己：

takeUntil :: (a -> Bool) -> [a] -> [a]
takeUntil p = go
    where go [] = []
          go (x:xs) | p x = [x]
                    | otherwise = x : go xs

或折叠：

takeUntil :: (a -> Bool) -> [a] -> [a]
takeUntil p = foldr (\x y -> x : if p x then [] else y) []

对于负数，collatz可能会陷入无限循环：

Prelude> hailstone (-7)
[-7,-20,-10,-5,-14,-7,-20,-10,-5,-14,-7,-20,-10,-5,-14,-7,-20,-10,-5,-14,

因此，我们可能希望更改所有小于或等于 的数字的条件1：

hailstone :: Integer -> [Integer]
hailstone = takeUntil (<= 1) . iterate collatz
  where collatz 1 = 1
        collatz n | even n = div n 2
                  | otherwise = 3 * n + 1
于 2019-10-11T18:58:01.580 回答
2

所有这些takeUntil, iterate, breakout的使用对我来说都有一种非常迫切的感觉（对数字做一些事情，直到你达到 1 - 然后我到底要怎么停下来？Haskell 等价的break语句是什么......？）

这并没有什么问题，它最终会起作用，但是在使用 Haskell 时，通常更好地考虑一下声明性：冰雹序列的尾部（除了[1]）是另一个（更短的）冰雹序列，所以hailstone n = n : hailstone (f n)对于某些人来说f

因此：

hailstone n
   | n == 1    = [1]
   | even n    = n : hailstone (n `div` 2)
   | otherwise = n : hailstone (3*n + 1)
于 2019-10-11T20:55:50.593 回答
1

似乎提供一些希望的唯一经典库函数是展开器。它使用 Maybe monad，返回Nothing是停止递归的原因。

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

您必须选择正确的函数参数：

import Data.List

hailstone :: Integer -> [Integer]

hailstone n = 
    let  next nn = if (even nn) then (div nn 2) else (3*nn+1)
         unfn nn = if (nn==1) then Nothing else let nx = next nn in Just (nx,nx)
    in
         n : (unfoldr unfn n)

main = do
    putStrLn $ "hailstone 7 is: " ++ show (hailstone 7)

这样，停止标准与后继功能明显分离。

于 2019-10-12T01:09:59.057 回答