On 9/24/07, Matthew Brecknell <[EMAIL PROTECTED]> wrote:
> I believe Bas is correct, though it might be worth elaborating on what
> he means by "worst case".
I think worst case can be interpreted as meaning: all rows have length c.
Most of the "work" consists of applying (:) if we ignore pattern
matching. The number of applications of (:) can be calculated with the
following function:
-- Number of rows after transposing plus the sum of the length of those rows
numApps xss = let t = transpose xss
in (length t) + sum (map length t)
Consider:
-- 3 rows, max 10 columns
transpose [ "1234567890"
, "123"
, "123"
]
> ["111", "222", "333", "4", "5", "6", "7", "8", "9", "0"]
26 applications of (:)
The number of applications of (:) is greatest when all lists have equal length.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
