斐波那契位表示 Haskell

Question

我已经具备以下功能

toBin, auxBin :: Integer -> [Integer]
toBin 0 = [0]
toBin n = reverse (auxBin n)

auxBin 0 = []
auxBin n = n `mod` 2 : auxBin (n `div` 2)

fib :: Int -> Integer
fib n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibonacci = [fib n | n <- [0..]]

但是当我用 toBin 函数映射 Fibonacci 列表时，我得到了一个不正确的列表：

因为，我得到了这个：

[[0],[1],[1],[1,0],[1,1],[1,0,1],[1,0,0,0],[1,1,0,1],[1,0,1,0,1],[1,0,0,0,1,0]]

但是，我想要这个：

[0,1,10,101,1010,10101,101010,1010101,10101010,101010101]

你能帮帮我吗？

Answer 1

有多种方法可以将数字相加得到一个数字。这是一种方法。可能不是最有效的方法，但另一方面是从较小的函数构建的。

像[1,0,1]、[1,0,0,0]和[1,1,0,1]这样的值本身就是列表，所以我们首先要做的是对它们进行索引。唯一的麻烦是我们想按降序对它们进行索引。你可以通过反转它们，索引它们，然后再次反转它们来做到这一点，例如：

Prelude> reverse $ zip [0..] $ reverse [1,1,0,1]
[(3,1),(2,1),(1,0),(0,1)]

每个元组的第一个元素是数量级，所以你只需要让它成为十的幂：

Prelude> :m +Data.Bifunctor
Prelude Data.Bifunctor> reverse $ fmap (first (10 ^)) $ zip [0..] $ reverse [1,1,0,1]
[(1000,1),(100,1),(10,0),(1,1)]

现在您可以简单地将元组的元素相乘：

Prelude Data.Bifunctor> reverse $ fmap (uncurry (*) . first (10 ^)) $ zip [0..] $ reverse [1,1,0,1]
[1000,100,0,1]

最后，您可以将所有这些数字相加。其实不需要反转反转列表：

Prelude Data.Bifunctor> sum $ fmap (uncurry (*) . first (10 ^)) $ zip [0..] $ reverse [1,1,0,1]
1101

您可以将这样的组合放在一个函数中，然后将您的值映射到它上面。

一个更有效的解决方案可能是做一个左折叠（foldl），例如：

Prelude> foldl (\acc x -> (10 * acc) + x) 0 [1,1,0,1]
1101
Prelude> foldl (\acc x -> (10 * acc) + x) 0 [1,1,1]
111

Answer 2

一个想法可能是用十进制表示法表示二进制值。所以我们 "transform" 2 变成 10.

我们可以通过编写递归函数来做到这一点：

bintodec :: Integral i => i -> i
bintodec 0 = 0
bintodec i = (mod i 2) + 10 * bintodec (div i 2)

这仅适用于正值，但这并不是真正的问题，因为斐波那契数是正数。

现在我们已经有了斐波那契数列的定义，就像您的回答一样：

fibs :: Num n => [n]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

所以我们唯一还要做的就是 map fibs 的每个元素与 bintodec:

binfibs :: Integral i => [i]
binfibs = map bintodec fibs

那么前15个数字是：

Prelude> take 15 binfibs
[0,1,1,10,11,101,1000,1101,10101,100010,110111,1011001,10010000,11101001,101111001]

这里的好处是我们不使用任何二进制列表来处理它，而是继续在整数世界中工作，这通常更安全。

然而，根据第二个列表，这与斐波那契数列无关。从 0 开始，然后在数字的右端移动一个零或一个。

为此我们可以使用 iterate:

iterate (\x -> 10 * x + 1-(mod x 2)) 0

产生：

Prelude> take 15 $ iterate (\x -> 10 * x + 1-(mod x 2)) 0
[0,1,10,101,1010,10101,101010,1010101,10101010,101010101,1010101010,10101010101,101010101010,1010101010101,10101010101010]

斐波那契位表示 Haskell

Fibonacci Bit Representation Haskell

haskell

functional-programming

fibonacci