haskell - 生成一个数的连分数展开式的前 n 项

Question

编辑:@Downvoters:您至少可以告诉我如何改进这个问题吗？我已尽力而为，在我看来，在没有任何评论的情况下投反对票是没有建设性的。

我对 Haskell 还很陌生，作为练习，我正在尝试创建一个函数，该函数返回 x 的连分数展开式的前 n 项。第一个参数 x 可以是浮点或整数，第二个参数必须是 int。这是我到目前为止的代码，加载时没有错误:

continuedFraction x n | x < 0  = []
                      | n < 1 = []
                      | otherwise = [floor x] ++ (take n (continuedFraction (1 / (x - floor x)) (n-1) ) )

(我知道这不是很优雅，但这是我当时能想到的最简单的一个。)

一旦我实际使用该功能，例如continuedFraction 3.1415 4 我收到以下错误消息。谁能指出我的错误/解释该消息？

(我确实尝试用上述想法进行类型定义，但也没有成功:continuedFraction::(Num x) => x -> Int -> [Integer])

错误消息(在没有类型定义的情况下运行时):

*Main> continuedFraction 3.1415 4

<interactive>:86:1:
    Could not deduce (Integral a0)
      arising from a use of `continuedFraction'
    from the context (Integral t)
      bound by the inferred type of it :: Integral t => [t]
      at <interactive>:86:1-26
    The type variable `a0' is ambiguous
    Note: there are several potential instances:
      instance Integral Integer -- Defined in `GHC.Real'
      instance Integral Int -- Defined in `GHC.Real'
      instance Integral Word -- Defined in `GHC.Real'
    In the expression: continuedFraction 3.1415 4
    In an equation for `it': it = continuedFraction 3.1415 4

<interactive>:86:19:
    Could not deduce (Fractional a0) arising from the literal `3.1415'
    from the context (Integral t)
      bound by the inferred type of it :: Integral t => [t]
      at <interactive>:86:1-26
    The type variable `a0' is ambiguous
    Note: there are several potential instances:
      instance Integral a => Fractional (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      instance Fractional Double -- Defined in `GHC.Float'
      instance Fractional Float -- Defined in `GHC.Float'
    In the first argument of `continuedFraction', namely `3.1415'
    In the expression: continuedFraction 3.1415 4
    In an equation for `it': it = continuedFraction 3.1415 4

Answer 1

建议

如果您是 Haskell 的初学者，您应该遵守一些规则:

• 如果您有一个函数，请确保为其提供一个能够表达您的预期输入/输出的类型签名
• 如果有疑问，请坚持使用具体类型 Double超过类型类Fractional a
• 如果您的函数按预期工作，请删除类型签名或使用语言扩展 -XScopedTypeVariables和 ghci 来探索编译器推断的签名，以了解类型类

回答

现在让我们探索您的函数 - 您想要生成一个连分数，我假设您写下的用于生成它的公式是正确的。 Haskell 的功能足以对无限列表进行建模，因此让我们使用该功能并摆脱第二个参数并生成一个(可能)无限列表。

continuedFraction :: Double -> [Int]

所以我们看到 - 您正在期待 Double输入和结果[Int] ，即整数列表，我选择 Int为了简单起见 - 至于巨大的Integer我认为这个算法既不稳定又高效 - 并且使用 Double我猜真正的问题是浮点运算。

continued fraction x | x < 0     = []
                     | otherwise = let i = floor x
                                       x' = 1/(x - fromIntegral i)
                                   in i : continuedFraction x'

这是您想出的最简单的解决方案，您遇到的问题是

• i :: Int , x :: Double在 Haskell 中你不能减去不同类型的东西，没有自动装箱/自动强制。我们喜欢对这些事情的控制 - 编译器不够智能，无法推断出我们“显然”想要计算的内容(如果您使用 MS Excel，您会看到这会导致什么结果)。

• 这个问题的解决办法是显式转换fromIntegral :: Double -> Int在这种情况下

• 为了便于阅读，我还切换了 [a] ++至a :这是等效的，编写的内容更少，性能更高，但这里不关心性能

现在在 ghci 中使用该函数:ghci myfile.hs

> continuedFraction 3.1415
[3,.....] --infinite list
> take 4 $ continuedFraction 3.1415
[3,7,14,1]

现在您可以探索该功能了!

如何使用建议

{-# LANGUAGE ScopedTypeVariables#-}

module SO34830462 where

--continuedFraction :: Double -> [Int]
continuedFraction :: Double -> _
continuedFraction x | x < 0  = []
                    | otherwise = let i = floor x
                                      x' = 1/ (x - fromIntegral i)
                                  in i : continuedFraction  x'

ghci myfile.hs导致错误

GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling SO34830462       ( 34830462.hs, interpreted )

myfile.hs:6:32:
    Found hole ‘_’ with type: [t]
    [...]
               continuedFraction :: Integral t => Double -> [t]
    [...]
Failed, modules loaded: none.

它简单地告诉您 - “哦，您没有指定正确的类型签名”，但是 ghc 可以使用此类型签名。

您可以替换类型签名并对 Double 执行相同的操作参数，一点点探索功能。

如果您不确定从什么开始，您可以省略类型签名并调用 :t continuedFraction进行 ghci session 。