Haskell : reference to previously updated elements of list within the update function

Question

Say I have the following definitions

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

Assuming I have a hypothetical function (upd is for update)

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

All fine so far. Now let's say the updateBook function needs to refer to the updated book three books before it i.e updateBook for book at position 5 in bookshelf need to refer to book at position 2 (assume first three books need no such reference to update). No problem, I say, and modify my code as such:

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

What I need help is with is the prevBook function. Although I am not even sure if I am approaching this problem the right way. So, if you guys have any better suggestion to approach this problem differently, it would be highly appreciated

EDIT:

Thomas M. DuBuisson: Your solution won't work for me. Here's why: Assume initial shelf (all) state as

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"}

then (drop 3 partialUpdate) is (using only ids rather than entire book statement):

updBook 4
updBook 5
updBook 6
updBook 7
updBook 8

zipWith' ($) (drop 3 partialUpdate) (all) is :

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!

In my case, I need books 7 and 8 to be updated against already updated versions of book 4 and 5,not the un-updated ones. I hope you understand what I mean to convey.

Answer 1

there is no knots to be tied here, no back flow of information, no passing around of forward references to a not-yet-defined values. Quite the contrary, we refer back to the known, already computed values. It works even without lazy evaluation. This:

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

is all you need. All that it is "doing", is maintaining an explicit back pointer into a sequence being produced, three notches back. "Back pointers are easy", to quote the haskellwiki's page on tying the knot.

Each invocation of updBook receives two arguments here - one an item at position i+3 in the original list, and another a newly updated item at position i.

Compare it with this piece of Haskell lore:

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

There is no knot-tying going on here as well.

Answer 2

First thing: your updShelf is map updBook.

Second: I think that a list of books might not be the best data structure for your problem, because lists don't support random access operations. You might want to try using an array if you really need random access at any point in your computation—see Data.Array.

Now to my main point: the sort of thing you're trying to do—have a computation that consumes parts of its own result—is frequently referred to in the Haskell community by the names "tying the knot" or the "credit card transformation" (buy now, pay later). Basically, it boils down to the fact that the following sort of expression is valid in Haskell:

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

How can that possibly work? Well, first of all, as you certainly know, Haskell is lazy, so such a computation is not necessarily circular. Second, it doesn't work with just any computation; there has to be a non-circular, terminating order in which the substeps of the computation can be performed.

So for example, this cycle function makes a circular list out of xs by appending the result of cycle xs to xs:

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

The "tying the knot" pattern can be abstracted with the library function fix, which I show here together with its use:

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

So in your case, what I would recommend is:

• Use a lazy array (like Haskell's built-in Array type) to represent the Shelf; this gives you random access to elements.
• Use the knot-tying technique to refer to the result Array during the computation.

Answer 3

This trick is related to tying the knot: we'll use the answer while computing the answer. For the purposes of illustration, I'll use type Book = Int instead.

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

Now, in ghci, we can verify that updateShelf is really using the updated versions:

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

As you can see, the first three are 1+1, 10+1, and 100+1, and the remaining two are 1000+(1+1)+1 and 10000+(10+1)+1, and are therefore using the updated previous values, just as you'd hope.

Answer 4

Ok, here is a flexible way to achieve this:

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

Answer 5

As a recursive function, updShelf won't be able to access elements that it hasn't been passed (so if it gets a list that starts at bookFive, it won't have access to bookThree.

If you want to write the function recursively, you need to do some more pattern matching:

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

updBook :: Book -> Book -> Shelf
updBook twoEarlier current = {- undefined -}

Answer 6

You can do this in two parts, first you partially apply updBook to all books, thus making a list of functions then you apply each of those functions to the proper previous book via a 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

Notice this has odd behavior at the start - it just makes the new list three elements shorter because of the drop 3. That isn't required, you could make that line read zipWith ($) partialUPdate (drop (len-3) (cycle all)), but you never specified what happens at the start of the list where there are no previous books.