Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is this pattern of folding and iteration?

Imagine you need to fold over a sequence, and want to know also the intermediate values at several points along the range. This is what I've used for this:

[a,b,c] = map fst . tail $ chain [g i, g j, g k] (zero, sequence)

g :: Integer -> (a,b) -> (a,b)

chain (f:fs) x = x : chain fs (f x)
chain [] x = [x]

The function g consumes a specified portion of an input sequence (of length i, j, etc.), starting with some initial value and producing results of the same type, to be fed into the next invocation. Consuming the sequence several times for different lengths starting over from the start and same initial value would be inefficient, both time and space-wise of course.

So on the one hand we fold over this sequence of integers - interim points on the sequence; on the other hand we iterate this function, g. What is it? Am I missing something basic here? Can this be somehow expressed with the regular repertoire of folds, etc.?

EDIT:  Resolved:  the above is simply

[a,b,c] = map fst . tail $ scanl (flip g) (zero, sequence) [i, j, k] 

interesting how a modifiable iteration actually is folding over the list of modifiers.

like image 363
Will Ness Avatar asked Mar 18 '12 18:03

Will Ness


2 Answers

Try scanl: http://www.haskell.org/hoogle/?hoogle=scanl

scanl is similar to foldl, but returns a list of successive reduced values from the left:

scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]

Note that

last (scanl f z xs) == foldl f z xs
like image 145
Marcin Avatar answered Sep 30 '22 19:09

Marcin


To elaborate on Marcin's comment, you basically want:

intermediates = scanl step zero sequence
map (\n -> intermediates !! n) [i, j, k]

step is not g, but rather just the part of g that consumes a single element of the list sequence.

Also, accept Marcin's as the correct answer.

like image 42
Gabriella Gonzalez Avatar answered Sep 30 '22 19:09

Gabriella Gonzalez