1

我是 Haskell 的业余爱好者,试图遍历“x”平方根的无限近似值列表,其中“acc”代表此步骤所在的世代。但是,当我运行下面的代码时,我得到了潜在的错误。

as' x acc = ( last(take (acc-1) (as' x (acc-1)))
+ (acc / last(take (acc-1) (as' x (acc-1)))) ) / 2 : as' x (acc+1)

ERROR "a5.hs":34 - Instance of Fractional Int required for definition of as'

此外,当我尝试应用此类型代码时,出现错误:

as' :: Float -> Float -> Float

Type error in application
*** Expression : (last (take (acc - 1) (as' x (acc - 1))) + acc / last (take (acc - 1) (as' x (acc - 1)))) / 2 : as' x (acc + 1)
*** Term : as' x (acc + 1)
*** Type : Float
*** Does not match : [a]

编辑:为了让您更清楚,我想在列表的上下文中使用此功能。例如 x = [1, as' x 2]。这个想法是这将积累一个无限的列表,因为 as' 将递归地调用自己。因此,为什么我觉得我可以在这里的列表上进行操作。

谁能给我一些澄清?

4

2 回答 2

12

的类型签名take

take :: Int -> [a] -> [a]

这是您的使用方式take

take (acc-1) (as' x (acc-1))

所以我们可以得出结论

(acc-1)         :: Int    -- first parameter to `take`
acc             :: Int    -- therefore

(as' x (acc-1)) :: [a]    -- second parameter to `take`, we don't know what `a` is

但是你的代码说

as' :: Float -> Float -> Float
as' x acc = ...

我们从中推断

x               :: Float  -- first parameter to `as'`
acc             :: Float  -- second parameter to `as'`
(as' x (acc-1)) :: Float  -- result of `as'`

这导致了几个矛盾:

  • acc不能同时是 a和IntaFloat
  • (as' x (acc-1))不能同时是 an[a]和 a Float---这是第二条错误消息试图告诉你的

最终,您正在尝试使用take不是列表的东西。我不确定您要做什么。


你可能想要签名

as' :: Float -> Int -> [Float]

那应该(我没有测试过)修复了上面的类型错误,但仍然留下了一个更基本的问题:每当你计算列表的第n个元素时,你都会重新计算列表的 *n-1* 个元素两次(等等,回到列表的开头:重新计算的指数增长),即使这个元素可能已经被计算过了。没有共享正在进行。

例如考虑

as' x acc = ( prev + (acc / prev) ) / 2 : as' x (acc+1)
  where prev = last(take (acc-1) (as' x (acc-1)))

这仍然是低效的:您仍然重新计算列表的先前元素。但是现在您只在计算下一个元素时重新计算所有先前的元素一次。

(如果我不指出last(take (acc-1) (as' x (acc-1)))可以简化为. 也是我的疏忽(as' x (acc-1)) !! (acc-2)。)


生成每个元素仅依赖于前一个元素的无限列表的常用方法是使用iterate.

复杂之处在于每个元素都依赖于累加器以及依赖于前一个元素。我们将通过将累加器合并到列表的每个元素中来解决这个问题。完成后,我们将丢弃累加器以生成最终的无限列表。

approxRoots :: Float -> [Float]
approxRoots x = map fst $ iterate next (x, 1)
      -- I don't know what your initial approximation should be
      -- I've put `x` but that's probably wrong
  where next (prev, acc) = (prev + acc / prev, acc + 1)
        -- First element of each pair is the approximation,
        -- second element of each pair is the "accumulator" (actually an index)
        -- I've probably transcribed your formula wrongly
于 2012-12-21T11:17:13.127 回答
7

dave4420 的回答已经很好了,我只是想分享一下如何从编译器给你的错误消息中获得最大的收益。又是这样:

*** Expression : (last (take (acc - 1) (as' x (acc - 1))) + acc / last (take (acc - 1) (as' x (acc - 1)))) / 2 : as' x (acc + 1)
*** Term : as' x (acc + 1)
*** Type : Float
*** Does not match : [a]

这意味着as' x (acc + 1)长表达式中的部分应该产生一个列表,但它实际上给出了一个Float值。

  • 为什么编译器希望它是一个列表?好吧,让我们看看该术语在表达式中的使用位置:

    (last .... ) / 2 : as' x (acc + 1)
    

    即,它被用作函数的第二个参数(:),并且编译器知道该函数的第二个参数必须是一个列表(编译器知道 is 的签名 (:)虽然a -> [a] -> [a]它没有在错误消息中提及该部分) .

  • 为什么它实际上是一个Float?由于您没有提供函数签名,因此编译器会为您推导出它并实际打印它:

    as' :: Float -> Float -> Float
    

    因此,编译器确定as'接受两个Float值并产生一个Float值。我不知道为什么会这样。

我的建议是通过自己明确写下函数签名来开始调试此问题。这样做会导致不同的错误消息,这更接近于您的期望与实际代码不匹配的原因。

于 2012-12-21T12:02:45.370 回答