9

说我有以下定义

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

假设我有一个假设函数（upd 用于更新）

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

到目前为止一切都很好。现在假设 updateBook 函数需要在它之前引用更新的书三本书，即书架中位置 5 的书的 updateBook 需要引用位置 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）是（仅使用 ids 而不是整个 book 语句）：

updBook 4
updBook 5
updBook 6
updBook 7
updBook 8

zipWith' ($) (drop 3 partialUpdate) (all) 是：

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!

就我而言，我需要根据已经更新的第 4 和第 5 本书的版本来更新第 7 本书和第 8 本书，而不是未更新的。我希望你明白我的意思。

4

6 回答 6

11

这个技巧与打结有关：我们将在计算答案时使用答案。出于说明的目的，我将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, and 100+1，其余两个是1000+(1+1)+1and 10000+(10+1)+1，因此正如您所希望的那样使用更新的先前值。

于 2012-08-27T17:22:13.390 回答
6

这里没有要打的结，没有信息的回流，没有对尚未定义的值的前向引用传递。恰恰相反，我们回溯到已知的、已经计算的值。即使没有惰性评估，它也可以工作。这：

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

是你所需要的全部。它所“做”的只是维护一个指向正在生成的序列的显式反向指针，向后三个缺口。“反向指针很容易”，引用haskellwiki 的关于打结的页面。

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

将其与这段 Haskell 传说进行比较：

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

这里也没有打结。

于 2012-08-28T07:14:20.167 回答
5

第一件事：你updShelf是map updBook.

第二：我认为书籍列表可能不是解决问题的最佳数据结构，因为列表不支持随机访问操作。如果您确实需要在计算中的任何点进行随机访问，您可能想尝试使用数组 - 请参阅Data.Array.

现在谈谈我的主要观点：你正在尝试做的那种事情——让计算消耗它自己的部分结果——在 Haskell 社区中经常被称为“打结”或“信用卡转换”。 "（现在购买，稍后付款）。基本上，归结为以下类型的表达式在 Haskell 中是有效的：

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

这怎么可能行得通？嗯，首先，正如你肯定知道的，Haskell 是惰性的，所以这样的计算不一定是循环的。其次，它不适用于任何计算；必须有一个非循环的终止顺序，计算的子步骤可以在其中执行。

因此，例如，此函数通过将结果附加到来cycle创建一个循环列表：xscycle xsxs

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。
于 2012-08-27T17:32:01.683 回答
2

您可以分两部分执行此操作，首先将 updBook 部分应用于所有书籍，从而制作一个函数列表，然后通过 zip 将这些函数中的每一个应用于正确的上一本书：

updShelf :: Shelf -> Shelf
updShelf [] = []
updShelf all@(book:books) = 
    let partialUpdate = map updBook all :: Book -> Shelf
    in zipWith ($) (drop 3 partialUpdate) all

updBook :: Book -> Book -> Shelf
updBook = undefined

请注意，这在开始时有奇怪的行为——它只是使新列表的三个元素更短，因为drop 3. 这不是必需的，您可以将该行设置为 read zipWith ($) partialUPdate (drop (len-3) (cycle all))，但您从未指定在列表开头没有以前的书籍时会发生什么。

于 2012-08-27T15:36:47.030 回答
2

作为递归函数，updShelf将无法访问它尚未传递的元素（因此，如果它获得一个从 开始的列表bookFive，它将无权访问bookThree.

如果你想递归地编写函数，你需要做更多的模式匹配：

updShelf :: Shelf -> Shelf
updShelf (bookOne : bookTwo: bookThree : books) 
    = (updBook bookOne bookThree) : (updShelf $ bookTwo : bookThree : books)

updBook :: Book -> Book -> Shelf
updBook twoEarlier current = {- undefined -}
于 2012-08-27T16:20:37.510 回答
2

好的，这是实现此目的的灵活方法：

updateOne book = undefined
updateTwo prevUpdatedBook book = undefined

updateBooks books = answer
  where numEasy = 3
        (easy,hard) = splitAt numEasy books
        answer = mapOnto updateOne easy (zipWith updateTwo answer hard)

-- More efficient that (map f xs ++ end)
mapOnto f xs end = foldr ((:) . f) end xs
于 2012-08-27T17:26:11.883 回答