[<<][staapl][>>][..]
Sat Jun 21 12:10:04 CEST 2008

avoiding O(N^2)

The problem of combining binchunks when they are consecutive is
interesting: I can't find a way to use my usual collection of higher
order functions without running into O(N^2) complexity due to iterated
append.

The problem: given a list of address/code pairs, create a new list
which combines them if they are consecutive.

((a c) (a c) ...)

To avoid N^2 and multiple traversals, the easiest way to do this is
using a state machine with an accumulator, but is it possible to use
HOFs for this, other than fold (which just factors out the explicit
recursion/looping), with the choice of using constant space (left
fold) or minimal hassle (right fold).

Maybe i need to look into parser combinators, or try to write one
figuring out the core routines.

On the other hand, the right abstraction for this might be stream
processing: convert binchuncks to a stream of word/address pairs, and
recobine them.

Let's try that first. Looks like i'm looking for 'for/fold'

This is actually an interesting point where first order functions are
syntactically more convenient than higher order ones ('for' is a
form!). The difference seems really syntax: it's probably
straighforward to convert between HOF and comprehension form.

In the guide: 11.8 Iteration Performance. Looks like they've been
thinking about optimization too :)

This actually looks like a good candidate for a ``pre-scheme'' style
first order language that compiles to straight machine code without
runtime support.

I don't understand why there is no 'in-append'. This would be a nice
exercise for sequence combinators.



[Reply][About]
[<<][staapl][>>][..]