efficiency, deep lists

[Richard Carlsson]

On Wed, 3 Oct 2001, Ulf Wiger wrote:

> Uhm, perhaps you're seeing something I don't...?
> Anyway, I did the following:
> 
> 9> Keys = lists:seq(1,10). 
> [1,2,3,4,5,6,7,8,9,10]
> 10> continuation:get_values(Keys).
> [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9|...]
> 11> continuation:get_values2(Keys).
> [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9|...]
> 12> v(10) == v(11).
> true
> 
> and therefore concluded that the functions were equivalent,
> without any deeper code analysis.

If the input has the form [[a,b,c],[d,e,f],[g,h,i]], the version using
foldl and ++ yields [g',h',i',d',e',f',a',b',c'], since it appended to
the left. However, appending to the right would give quadratic
behaviour. Changing to foldr would solve it.

	/Richard

Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/