Assuming that foldr should be used to build data structures and foldl' if the result is supposed to be a single value, I'm not sure what to use for Strings. On the one hand it is a data structure, but on the other hand a String is usually only used as a whole, meaning that short-circuiting isn't very relevant. To answer this question, it's probably crucial how functions like putStrLn use Strings, isn't it? Or am I on a completely wrong track?

EDIT: So I want my function to turn something like [(5, 's'), (1, ’a'), (3, 'd')] into sssssaddd (following an exercise from https://en.m.wikibooks.org/wiki/Haskell) and I have to choose one from those two functions:

decode :: [(Int, Char)] -> String
decode = foldr ff []
  where
    ff (l, c) xs = replicate l c    xs

decode' :: [(Int, Char)] -> String
decode' = foldl' ff []
  where
    ff xs (l, c) = xs    replicate l c

CodePudding user response：

You're on the completely wrong track. The only correct way to decide what fold to use involves knowing what the fold will do. Knowing only the output type is not enough.

CodePudding user response：

A String is just an alias of [Char], so a list. If you use foldl or foldl' with append (( )) or cons ((:)), it will fold with foldl as:

(("hell"    "o")    " ")    "world"

Concatenating takes linear time in the length of the left operand. So if you eacn time concatenate a single character, then constructing a string of n characters will take O(n²) time.

Another problem that might arise if you have an infinite list, in that case, foldl will get stuck in an infinite loop. Whereas in foldr you can "consume" the output if that happens in a generator-like approach.

But as @chepner says, using Strings for large amounts of text is not effective: it requires a cons per character, so it blows up in memory. Text allows one to have a more compact and efficient way to store text, in an unboxed type, and often the algorithms are more efficient than what one can do with a String.