1

我对解决问题的实际解决方案或其他方法不感兴趣，这是我需要帮助的记忆:)

我需要帮助解决记忆化的帕斯卡三角问题。我想得到三角形底部的中间数字。（欧拉计划 15）

第一个例子没有被记忆（虽然名字是这样暗示的）“20 20”不可解

第二次尝试是尝试做类似的事情：http ://www.haskell.org/haskellwiki/Memoization

第三是关于 no2 的 hlints 建议，如果这对某人来说更具可读性。

我收到这个错误，但我不确定它是否正确，即使它会编译......（从 ghci 运行，以 2 2 作为参数

no instance for (Num [a0])
arising from a use of `zmemopascals'
Possible fix: add an instance declaration for (Num [a0])
In the expression: zmemopascals 2 2
In an equation for `it': it = zmemopascals 2 2

.

Code:
--1 
memopascals r c =  [[pascals a b | b<-[1..c]] | a<-[1..r]] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1) 

--2 
--xmemopascals :: Int -> Int -> Int 
xmemopascals r c =  map (uncurry pascals) (zip [1..] [1..]) !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1) 


--3 
zmemopascals r c =  zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1)
4

3 回答 3

2

Memoization 在您的函数中不起作用，因为像这样的调用memopascals 5 5会在内部构建三角形的一部分并从中返回单个值。另一个调用与 .mempascals 6 6内部的那个部分三角形没有任何联系memopascals 5 5。

为了有效的记忆，您希望将公共部分（如表示三角形中计算的数字的列表列表）放在一个单独的函数中，然后由访问特定索引的函数使用。这样，您可以使用相同的列表列表来查找不同的索引。

通常最简单的方法是编写一个fullpascals :: [[Int]]生成完整（无限）数据结构的函数，然后编写另一个函数来访问该数据结构，例如

memopascals x y = fullpascals !! (x-1) !! (y-1)

在您的情况下fullpascals，将与您当前的功能之一相同，但没有特定索引的参数。它甚至可以memopascals在内部用于递归。

旁注：在memoized_fibwiki 的示例中，被记忆的“公共部分”不是直接所有 fib 的列表，而是访问所有 fib 列表的函数。效果是一样的，因为编译器足够聪明，可以优化它。

于 2012-07-13T15:29:35.557 回答
1 
zmemopascals r c =  zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1)

并不是说它对错误很重要，但在最后一行，你想调用zmemopascals而不是memopascals.

在第一行中，您有两个列表索引运算符。所以zipWith pascals [1 .. ] [1 .. ]必须有[[a]]一些类型a。pascals说的定义

pascals :: Num t => Int -> Int -> t

因此zipWith pascals [1 .. ] [1 .. ] :: [t]. 因此类型推断找到了t = [a]，但编译器没有找到实例Num [a]。

对于记忆，您必须为完整的三角形命名，就像@sth 建议的那样，以避免重新计算（斐波那契记忆仅起作用，因为编译器足够聪明，它的形式不能保证）。

另一种选择是使用iterate,构造三角形

pascal :: Int -> Int -> Integer
pascal n k = iterate nextRow [1] !! n !! k
  where
    nextRow ks = zipWith (+) (0:ks) (ks ++ repeat 0)
于 2012-07-13T15:35:03.200 回答
1

有几个实现记忆的指导方针（看看这里最近的一些讨论）。

首先，在 GHC 编译器中使用 -O2 优化标志。其次，使用单态类型签名。命名您想要实现共享的中间列表。

然后，注意您的嵌套定义。如果嵌套定义依赖于其封闭（“外部”）范围内的参数值，这意味着对该外部函数的每次调用都必须重新创建其所有嵌套定义，因此不会有任何一个列表要共享，但有许多独立的独立的。

在您的函数中，分离并命名您想要共享的列表表达式，我们得到

memopascals r c = xs !! (r-1) !! (c-1) 
 where
   xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = memopascals (x-1) y + memopascals x (y-1)

您的xs定义取决于rand的值c，但是您memopascals从嵌套的函数 中调用“外部”函数pascals。的每次调用memopascals 都必须创建自己的副本，xs因为它依赖于memopascals的参数，r并且c. 无法分享。

如果您需要该依赖定义，则必须安排不要调用“超出范围”，而是留在该范围内，以便可以重用所有内部（“嵌套”）定义。

memopascals r c = f r c
 where
   f r c = xs !! (r-1) !! (c-1)
   xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = f (x-1) y + f x (y-1)

现在，每次调用memopascals都会创建其内部定义（从其嵌套范围），然后它们相互调用，从不超出范围 - 因此列表xs被重用，实现共享。

但是另一个调用memopascals将创建它自己的列表内部定义的新副本xs，并将使用它。我们可以称之为“本地”共享，而不是“全局”共享（即记忆化）。这意味着它运行速度很快，但第二次调用相同参数的时间与第一次调用的时间相同——而不是完全记忆化的 0 时间。

只有一种方法可以实现这一点，那就是让你的xs定义独立。然后编译器可以将所有嵌套范围框架粉碎在一起，执行lambda 提升将嵌套闭包转换为普通lambda等：

memopascals :: Int -> Int -> Integer
memopascals r c = [[pascals a b | b<-[1..]] | a<-[1..]] !! (r-1) !! (c-1) 
 where 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = memopascals (x-1) y + memopascals x (y-1)

使用 -O2 开关，即使对于这个版本，GHC 也会执行完整的记忆。只要我们不忘记单态类型签名（或者它又是本地共享）。

于 2012-07-17T00:02:27.250 回答