Haskell:引用更新函数中先前更新的列表元素

Question

说我有以下定义

data Book = Book {id :: Int, title :: String}
type Shelf = [Book]

假设我有一个假设函数(upd用于更新)

updShelf :: Shelf -> Shelf
updShelf all@(book : books) = updBook book : updShelf books

到目前为止都很好.现在让我们说updateBook函数需要在它之前参考更新的书籍三本书,即书架中位置5的bookBook for book需要参考位置2的书(假设前三本书不需要这样的参考更新).没问题,我说,并修改我的代码:

updShelf :: Shelf -> Shelf
updShelf all@(book : books) prevBook = updBook book prevBook : updShelf books
                where prevBook = ???

我需要帮助的是prevBook功能.虽然我甚至不确定我是否正确地接近这个问题.所以,如果你们有任何更好的建议以不同的方式解决这个问题,我们将非常感激

编辑:

Thomas M. DuBuisson:你的解决方案对我不起作用.原因如下:假设初始货架(全部)状态为

Book {id=1, title="a"}
Book {id=2, title="b"}
Book {id=3, title="c"}
Book {id=4, title="d"}
Book {id=5, title="e"}
Book {id=6, title="f"}
Book {id=7, title="g"}
Book {id=8, title="h"}

那么(drop 3 partialUpdate)是(仅使用id而不是整本书语句):

updBook 4
updBook 5
updBook 6
updBook 7
updBook 8

zipWith'($)(drop 3 partialUpdate)(全部)是:

updBook 4 1
updBook 5 2
updBook 6 3
updBook 7 4 -> YIKES! Older version of book 4!
updBook 8 5 -> YIKES! Older version of book 5!

在我的情况下,我需要更新第7和第5册的已更新版本的书籍7和8,而不是未更新的书籍.我希望你理解我的意思.

Answer 1

这个技巧与打结有关:我们将在计算答案时使用答案.出于说明的目的,我将type Book = Int改为使用.

updateShelf :: Shelf -> Shelf
updateShelf shelf = answer where
   answer  = zipWith updateBook shifted shelf
   shifted = replicate 3 Nothing ++ map Just answer

-- some stupid implementation just for illustration
updateBook :: Maybe Book -> Book -> Book
updateBook Nothing          current = current + 1
updateBook (Just threeBack) current = current + threeBack + 1

现在,ghci我们可以验证updateShelf是否真的使用了更新版本:

*Main> updateShelf [1,10,100,1000,10000]
[2,11,101,1003,10012]

正如你所看到的,前三个是1+1,10+1和100+1,其余两个是1000+(1+1)+1和10000+(10+1)+1,因此被使用更新之前的值,就像你希望.

Answer 2

这里没有结点,没有信息的回流,没有传递对尚未定义的值的前向引用.恰恰相反,我们回顾已知的已经计算的值.它甚至没有懒惰的评估.这个:

updShelf shelf@(a : b : c : t) = xs where
   xs = a : b : c : zipWith updBook t xs

是你所需要的全部.所有它正在"做",就是将一个显式的后向指针保持在一个正在生成的序列中,三个槽口回来."后退指针很容易",引用haskellwiki的关于打结的页面.

每次调用updBook都会在此处接收两个参数 - 一个是i+3原始列表中位置的项目,另一个是位置上新更新的项目i.

将它与这段Haskell传说相比较:

g (a,b) = xs where
   xs = a : b : zipWith (+) xs (tail xs)

这里也没有打结.

Answer 3

第一件事:你updShelf的map updBook.

第二:我认为书籍列表可能不是您问题的最佳数据结构,因为列表不支持随机访问操作.如果你真的需要在计算中的任何一点随机访问,你可能想尝试使用数组 - 请参阅Data.Array.

现在我的主要观点:你正在尝试做的事情 - 有一个消耗部分结果的计算 - 在Haskell社区经常被称为"打结"或"信用卡转换"的名称"(现在购买,稍后付款).基本上,它归结为以下类型的表达式在Haskell中有效:

let result = f result in result  -- apply f to its own result

怎么可能有用呢？好吧,首先,你当然知道,Haskell是懒惰的,所以这样的计算不一定是循环的.其次,它不适用于任何计算; 必须有一个非循环的终止顺序,其中可以执行计算的子步骤.

因此,例如,此cycle函数xs通过将结果附加到以下内容cycle xs来生成循环列表xs:

cycle xs = let result = xs ++ result in result

可以使用库函数抽象"绑结"模式fix,我在这里展示了它的用法:

fix f = let result = f result in result
cycle xs = fix (xs++)

所以在你的情况下,我建议的是:

• 使用惰性数组(如Haskell的内置Array类型)来表示Shelf; 这使您可以随机访问元素.
• 使用结打结技术Array在计算过程中引用结果.