TeXitoi wrote:

...

why is foldl used by Data.List for sum?

Daniel Fischer wrote:

Because Haskell is a non-strict language, and foldl' is strict -- someone might write a (legitimate) Num instance for a datatype such that foldl (+) 0 xs returns a good value, but foldl' (+) 0 xs gives ***Exception: Prelude.undefined for some lists xs.

It is possible to define such a Num instance, but it is extremely rare for anything like that to come up in practice.

However, with optimisations turned on... GHC knows that sum is actually strict

GHC does that when optimizations are turned on, but that behavior is not required by the Haskell standard. So there is no guarantee that any given compiler will produce usable output if you use foldl instead of foldl' for sum. In GHCi sum is broken, because optimizations are not in effect there. You have to define your own version of sum using foldl' for every GHCi session (or put it in your .ghci file). So it's a trade-off between a slight convenience in a bizarre corner case and general usability. I agree with Don that this is a bug in the Haskell 98 standard. Regards, Yitz

...

...

However, with optimisations turned on... GHC knows that sum is actually strict

GHC does that when optimizations are turned on, but that behavior is not required by the Haskell standard. So there is no guarantee that any given compiler will produce usable output if you use foldl instead of foldl' for sum.

In GHCi sum is broken, because optimizations are not in effect there. You have to define your own version of sum using foldl' for every GHCi session (or put it in your .ghci file).

So it's a trade-off between a slight convenience in a bizarre corner case and general usability. I agree with Don that this is a bug in the Haskell 98 standard.

I'm not sure whether it's a wart or a bug, but I agree that it would be better to have the default sum strict (and provide lazysum for the cases where it's useful).

That would be really inconsistent with the way the rest of the Haskell language and libraries works. Note that foldl' has a ' to indicate that it's not the same as foldl exactly. I would propose that sum' exist as well as sum, and that sum be lazy. Part of what's interesting about Haskell is the default non-strict evaluation of the language, and even if it's hard for newcomers to get used to it, they're better off having a consistent space to work in rather than all these exceptions to make algorithms like "sum" work more efficiently when the problem was one of documentation and education about the language. Of course if you want a strict functional language there's plenty of those out there. Dave

...

Regards, Yitz

Cheers, Daniel

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

...

Note that foldl' has a ' to indicate that it's not the same as foldl exactly. I would propose that sum' exist as well as sum, and that sum be lazy.

Well, meaningful identifier names is nice, but I think here we have a case of the code smell "type info embedded in the name". Strictness of a function should be expressed in the function's type instead. But that seems impossible with Haskell at the moment. (At best, we can express strictness of constructors?) Hence we have "underspecified" behaviour: Prelude Data.List> :t foldl' foldl' :: (a -> b -> a) -> a -> [b] -> a Prelude Data.List> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a and need to resort to the awkward workaround via naming conventions. Of course Haskell implementations do have some kind of strictness information (e.g., in ghc interface files), so it's not impossible to define some kind of annotation system. Although I did not check what the compiler's strictness info is for foldl and fold' - and what was actually needed (at the source level). The current textual definition (Data.List API docs: "foldl' = a strict version of foldl") is not too precise, either. Well, I guess there's a huge design space. But it's a huge problem (describing/controlling the behaviour of lazy programs). Best - J.W.

David Virebayre writes:

Even if we had a syntax to express that the function is strict, wouldn't we still need two distinct function names for the strict and lazy case ?

OK, I'd like to register a "code smell" for: "hierarchical/systematic structure inside identifier names"; suggested refactoring: use hierarchy/structure provided by the language, in this case, something like: Data.List.Strict.fold, Data.List.Lazy.fold Or - if we had static overloading, and strictness info in the type, then we wouldn't need different names. Can of worms ...

David Virebayre writes:

But then if you need both version, you will have to import them qualified, which I don't like much.

solution: type directed name resolution: * either in the language, http://hackage.haskell.org/trac/haskell-prime/wiki/TypeDirectedNameResolutio... * or, failing that, simulated by a helpful (type and module aware) IDE.

Johannes Waldmann writes:

Well, meaningful identifier names is nice, but I think here we have a case of the code smell "type info embedded in the name". Strictness of a function should be expressed in the function's type instead.

I've stumbled into this sentiment before, and it's one of those "I must be dumb because everybody else takes this for granted"-issues.¹ Are there any explanation of how/why this is a type issue? To me it appears natural to use the same higher order functions (say, foldr) with strict operations or lazy ones. OTOH, I can't off-hand think of a reasonable use for foldl or foldr', so you're probably right they should be separated.

Prelude Data.List> :t foldl' foldl' :: (a -> b -> a) -> a -> [b] -> a

Prelude Data.List> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a

What should the type look like? If memory serves, Clean allows bangs in type signatures, something like: foldl' :: (a -> b -> a) -> !a -> [b] -> a but I thought it just added a seq under the hood, much like bang patterns like foldl' f !z xs = ... do in Haskell, so it's not like !a is a separate type. Or? Let me explore a bit here. In deference to the time-honored if ill-advised tradition of abusing the apostrophe, let a' be the type a, but strictly evaluated. Perhaps things could look something like: foldl' :: (a' -> b' -> a) -> a' -> b (+) :: a' -> a' -> a -- strict (:) :: a -> [a] -> [a] -- non-strict foldl' (+) 0 [1..10] -- okay foldl' (flip (:)) [] [1..10] -- illegal Would something like this work? It seems to me that strictness doesn't apply to result types (x `seq` x === x), and you need to track the relationship between a and a', since you probably want to allow a lazy value as e.g. the second parameter of foldl'. I'm sure this has been discussed to death ages ago, is there a simple overview I might understand that discusses or summarizes the issue? -k ¹ As opposed to the "everybody else must be dumb, because they disagree with me"-issues. Perhaps I can work out my IQ from the ratio? -- If I haven't seen further, it is by standing in the footprints of giants

On Fri, 12 Mar 2010, Johannes Waldmann wrote:

Ketil Malde writes:

...

...

Prelude Data.List> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a

What should the type look like?

Good question - and in my posting I tried to avoid the impression that I have an answer, because I really haven't.

foldl' :: Seq a => (a -> b -> a) -> a -> [b] -> a ? I don't think that foldl' is really what we want, since we cannot control the depth of strictness.

Ketil Malde wrote:

What should the type look like? If memory serves, Clean allows bangs in type signatures, something like:

foldl' :: (a -> b -> a) -> !a -> [b] -> a

but I thought it just added a seq under the hood, much like bang patterns like

foldl' f !z xs = ...

do in Haskell, so it's not like !a is a separate type. Or?

The usual approach I've seen is not to distinguish strict and lazy datatypes, but rather to distinguish strict and lazy functions, e.g. by having two different arrows: (->) for lazy functions and (!->) for strict ones.[1] There are reasonable reasons for wanting to distinguish strict/lazy datatypes instead, though that's usually called distinguishing lifted vs unlifted types, which has different effects on the semantics. I don't recall which approach Clean uses.

Would something like this work? It seems to me that strictness doesn't apply to result types

Which is one benefit of the two arrows version: there's no way to talk about making the result strict.

and you need to track the relationship between a and a', since you probably want to allow a lazy value as e.g. the second parameter of foldl'.

Usually, if you're going to be distinguishing lifted and unlifted types then you'll want to be able to say that the unlifted values can always be coerced into the corresponding lifted type. Whether that involves subtyping, autoboxing, etc. will depend on the compiler and the language. [1] Actually, just having two is insufficiently expressive. What you actually want is to make the (->) type constructor take three arguments: the parameter type, the return type, and an index belonging to the set {Strict,Lazy}. That way you can use type variables to unify strictness behaviors of higher-order functions with their function arguments (i.e., the HOF is strict or lazy in various arguments depending on the strictness properties of the functional arguments). -- Live well, ~wren

Ben Millwood wrote:

In general, laziness behaviour can get complicated quickly and so I'm not convinced that the type signature is a good home for that information.

Certainly it can. A lot of the same problems arise in the logic programming community under the topic of "modes", i.e. whether a logic variable must be ground (or rather, how defined it must be) before it's safe to "run the function backwards". Though, at present AFAIK, they've contented themselves with rough approximations like lifted/unlifted value types or strict/lazy arrows, either of which can catch the simple cases. Personally, I think the only way to capture *all* strictness information is if we have full dependent types (or worse, for logic languages, since their dependencies lack the directionality of usual dependent types). If we had full dependent types, and went with the lifted/unlifted distinction instead of the strict/lazy one, then we could give `maybe` the type: maybe :: (_:b) -> (_:a -> b') -> (m:Maybe a) -> (case m of Nothing => b ; Just _ => b') Would such a type be helpful? <shrug> I think adding full dependent types is a bit much if all we're interested in is strictness behavior. But, as you say, it seems very unlikely that we can encode strictness behaviors which may depend on particular runtime values without DTs. -- Live well, ~wren

Am Freitag 12 März 2010 12:14:06 schrieb Paul R:

wren> I wish Haskell allowed ! to occur (non-initially) in alphanum_' wren> identifiers as well as in symbolic ones. Then we could be more wren> consistent about having ! mean strictness

BTW, does something in haskell syntax prevent '?' from appearing at the end of identifiers ?

Yes, http://haskell.org/onlinereport/lexemes.html#sect2 uniSymbol -> any Unicode symbol or punctuation Punctuation characters are symbols (as far as the lexical syntax is concerned), hence can't appear in varids, only in varsyms (operators).

Daniel Fischer wrote:

...

I'm not sure whether it's a wart or a bug, but I agree that it would be better to have the default sum strict

David Leimbach wrote:

That would be really inconsistent with the way the rest of the Haskell language and libraries works... I would propose that... sum be lazy...

Daniel meant "internally strict". All versions of "sum", even the current one, are strict in the literal sense: Prelude> sum undefined `seq` 42 *** Exception: Prelude.undefined As for how it works internally, there is no assumption in Haskell about that. Generally, it is up to the compiler to decide in each individual case. Here the correct thing to do in practice is to be strict, but only a very smart compiler like GHC with -O2 can figure that out. So the library should give that hint.

all these exceptions to make algorithms like "sum" work more efficiently when the problem was one of documentation and education about the language.

This is not a question of efficiency. The current version of "sum" is *broken* - it crashes programs. Haskell education would be far better served by removing bugs from the standard libraries than by needing to include rules like "Never use the standard 'sum' function unless you are absolutely certain that the input to the function will never exceed the stack size of your runtime." Regards, Yitz