Assembling lists start-to-end

[Hal Daume]

sorry, forgot to send this to the list:

Another way to do it is to use accumulating lists.

As a simple example, let's consider:

> myf p l =3D reverse (filter p l)

(myf Char.isUpper "Hello Cruel World"  =3D=3D> "WCH")

that is, it returns elements of a list which match the predicate in
reverse order.  we could write this very slowly using explicit recursion
as:

> myf2 p [] =3D []
> myf2 p (x:xs)
>    | p x       =3D myf2 p xs ++ [x]
>    | otherwise =3D myf2 p xs

but traversing the recusive list is very slow.  we might induce tail
recursion in something like:

> myf3 p l =3D myf3' l []
>   where
>     myf3' []     acc =3D acc
>     myf3' (x:xs) acc =3D myf3' xs (x:acc)

Now, the accumulator 'acc' holds the value we're going to return at the
end.

So this is pretty much what you want.

Now, suppose we're just doing filter without the reversing, but we still
want it to be tail recursive.  We might think we have to write:

> myf4 p l =3D reverse (myf3' l [])

(where myf3' is as before)

this is not so.  We can have fun with function composition.  What we do
is change the accumulator from a list to a function from a list to a
list.

> myf4 p l =3D myf4' l id
>   where
>     myf4' []     acc =3D acc []
>     myf4' (x:xs) acc
>         | p x        =3D myf4' xs (\l -> acc (x:l))
>         | otherwise  =3D myf4' xs acc

here, we start out the accumulator as the identity function.  to add an
element to it, we make a function which takes the old list, adds 'x' to
the front and then applies the accumulator.  in the base case, we simply
apply the empty list to the accumulator function.

the second-to-last line can be rewritten a bit more conveniently as:

>         | p x        =3D myf4' xs (acc . (x:))

the neat thing about this is that you can easily change the way the list
goes.  as it is, we have filter, but if we flip the order for (.), as
in:

>         | p x        =3D myf4' xs ((x:) . acc)

then we get (reverse . filter).

HTH

 - Hal

 --
 Hal Daume III                                   | hdaume@isi.edu
 "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume


> -----Original Message-----
> From: haskell-cafe-admin@haskell.org=20
> [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Mark Carroll
> Sent: Saturday, June 21, 2003 5:39 AM
> To: haskell-cafe@haskell.org
> Subject: Assembling lists start-to-end
>=20
>=20
> I am assembling a list from start to end. I can add elements=20
> to the end
> with "previous ++ [current]" or I can add them with "current=20
> : previous"
> and reverse it when I'm done. Or, maybe I should use some other data
> structure. (I don't know the length in advance.) Any thoughts?
>=20
> -- Mark
>=20
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>=20