In retrospect, was burning bridges a mistake?

#1

Branching off of OverloadedStringDefault proposal:

After thinking about it for a bit:

  • The only real Foldable / Traversable instances I can count in base are List and Array. Every other one is there to either extract 0-1 elements or to coerce away a newtype.

  • Data structure modules tend to be imported qualified, as their exports clash with Prelude. Map.foldr is as good as foldr in my mind, as these functions are used sparsely.

  • Data structures do not need all of the functions:

    • foldl / foldr' for List are the classic example, indeed not all datatypes are born symmetric;
    • For non-empty types null is always False and toList has one or more elements guaranteed;
    • elem / maximum / minimum / sum / product are List processing functions and there is no expectation for other datatypes to implement any of them;
    • foldMap' is a complete mystery to me (isn’t it always a strict fold around a monoidal accumulator?).

  • Monomorphic / indexed / existential / higher-kinded stuff does not fit these definitions and thus either chooses to go the simple way or branches out into a whole extended bridge-burning universe that suffers from the exact same issues.

The ideas around Foldable / Traversable and their extensions are solid, and libraries should be encouraged to share them. Explanations of terminology and mathematical reasoning should be documented somewhere easily accessible, but typeclasses are not a good tool here.

And yes, I know, even if most of the community fervently agrees with this, these typeclasses will not be dismantled overnight. If base-5 were to be agreed upon, I could see this be one of the changes.

2 Likes
#2

I don’t know exactly what you mean by this, but I find these functions very useful for other types like Set.

And I think where the advantage really appears is with derived functions like any, all, and, or, traverse_ etc. There are so many of these and for many data structures the most efficient implementation can be derived directly from the fold, so I appreciate that not every data type has to define all these functions over and over again.

And then there is Traversable which is the answer to every Haskell question and the cornerstone of the lens library. I think that is an even more principled and fundamental type class than foldable and certainly wouldn’t want to see it removed.

5 Likes
#3

I mean that with most data structures you can do List.product . Data.toAscList and gain exactly the same results with roughly the same performance.

Set is a bit special in this respect, since it has natural fast elem / maximum / minimum, but the actual proper definitions there are lookupIndex / lookupMin / lookupMax, all with completely different constraints (and elem with a different implementation because of Eq).

I too am used to the composability this provides without regard for the underlying datatype, but it’s very hard to estimate how much of this usage is just Lists. I feel like the answer to that is “a lot”, so I don’t think it’d change much if I had to be just a tad more specific.

2 Likes
#4

Traversable is much closer to Functor in my mind because it preserves the shape of the datatype. It is admittedly quite weird that its superclasses are Functor and Foldable, yet definitions require Applicative or Monad, but I don’t have any opinions on this.

Also now that I think about it FunctorWithIndex and TraversableWithIndex could just be written as Traversable threading an accumulator, so I it indeed is a very powerful abstraction.

1 Like
#5

Foldable (or rather, its methods) features heavily in Haskell Intros. Then it’s a wot? that these are instances:

  • Either – furthermore length $ Left 1 returns zero; length $ Right 2 returns 1; maximum $ Left 1 returns exception empty structure – whatever the heck that’s supposed to tell me; maximum $ Right 2 returns 2 without demur.
  • (,) – length (1, 2) returns 1; maximum (5, 2) returns 2.
  • Maybe – maximum $ Nothing returns the same exception empty structure.

Now the so-and-so who introduced all this nonsense claimed it was the “only sensible” set of instances.

Prior to FTP, those uses would have been rejected as type errors; and I think that’s entirely correct at beginners level – continuing that would have been at least as “sensible” an approach. It’s embarrassing that a language claiming to have strong typing disciplines – and to that end is contemplating restricting head, tail – gives run-time errors for clearly stupid code. (If an advanced programmer wants to do fancy traversals over heterogeneous structures including those types; I think the onus is on them to say so/import instances for that.)

In particular length should have remained restricted to Lists (in H98 it’s a straightforward function, not a method). There should have been a differently named method (size?) introduced to Foldable.

2 Likes
#7

You can get static warnings by using Stan: STAN-0207. Maybe that inspection should be built into GHC as a warning.

1 Like
#8

Actually since Traversable folds in a direction, why aren’t there right/strict variations as well? One particular issue I came across is that there is no clear guidance on whether the datatype internals should be evaluated as part of the action or separately (compare seq x (pure (Foo x)) and pure (seq x (Foo x))).

I also don’t think typeclasses are the only way of solving these things. If type Traverse f t a b = (a -> f b) -> t a -> f (t b) were a general function shape in base people would be able to write their own foo :: Applicative f => Traverse f Foo a b -> _ functions, which would also allow the freedom to mix and match definitions at will.

#9

Oh sure. I could define my own function listLength; I could NoImplicitPrelude and import it qualified; …

There’s probably all sorts of ways I could make a beginner’s experience more perplexing. I look at the hoops proposers have to jump through these days to not break backwards compatibility. The time it was needed was when you-know-who just rode roughshod over everybody, with little/no consultation. (And the latest I hear is that GHC20xx was never intended to help beginners. Why don’t we just put a big sign outside the front door: ‘Beginners go away!’ ?)

#10

Stan was and will be again soon included in HLS so most beginners should get those kinds of warnings without many hoops.

#11

I feel like not having these kinds of issues in the first place is preferable to piling up linters that hopefully will illuminate to you another zany language quirk. Obviously this doesn’t apply uniformly, e.g. you can’t “fix” laziness out of Haskell, but overzealous typeclass usage seems to be one of the most consistent issues in the language.

This is where things get complicated. Typeclasses seem to exist specifically to ease language use and, indeed, when applied correctly they work great: (+) / (-) / (*) are well-defined for all basic numeric types and noone gets confused using them. When applied incorrectly you get runtime errors, incorrect results, unwanted instances, dependency bloat and terrible Hackage documentation.

Beginners, alas, will have to suffer no matter what: with fewer typeclasses they’d have to browse more docs and write slightly more complex code, not to mention having to “relearn” everything else base-5 could introduce. While a more rigorous approach would inevitably help beginners, I feel like a lot of people would view it as making things more complex for no visible benefit.

1 Like
#12

Pretty much of all these functions are just f . toList. There is no real benefit of creating a typeclass just for that. For the few exceptions like mininum for Set, if a rewrite rule is not enough (if it’s not, why ?), then setMinimum is as good.

#13

I agree (as long as the library authors make sure the list will be fused away). I hadn’t really considered that as an alternative from reading the original post.

1 Like
#14

Your q is (or at least was) about the churn from a dramatic re-structuring of typeclasses. length originally wasn’t in a typeclass, and I see no reason why it got dragged into them. “length” (as a word in English) strikes me as not applicable to a fixed-size container like a Maybe or a pair.

Yes, burning bridges introduced runtime errors, yada, yada to a situation which didn’t have any of that.

Now you’ve lost me. Somebody is proposing restructuring typeclasses to (allegedly/aot) help beginners?

The learning from the burning bridges debacle was (I thought)

  • the resulting design was wrong, and that could have been identified with wider consultation (although there was a consultation process for the core language, for Libraries not so much);
  • the execution of the change was terrible, with next to no advance warning;
  • the ‘benefits’ from the change were marginal to none for many users (esp. beginners);
  • widely-used intro material was not revised (in many cases still hasn’t been revised), causing persisting bafflement (again especially for beginners);
  • runtime errors, incorrect results, unwanted instances, …

Is it worth addressing the “wrong” design and causing more churn? Probably not. Probably we should be changing Haskell Intros to focus less on Lists, and focus more on tailored data structures; and then move to generic comprehensions (Foldable, Traversable). But all that Lisp heritage …

1 Like
#15

From the perspective of someone who teaches about 200 beginners every year, FTP has caused absolutely zero issues or consternation for students, and I would encourage people to step away from “won’t someone think of the beginners?” as a necessary failing of FTP.

There are plenty of things that students do stumble over in Haskell, and I have advocated on those elsewhere—but this isn’t one of them :slight_smile: (To pick an arbitrary example, the numeric hierarchy causes issues from day one! fromInteger vs fromIntegral vs realToFrac vs round vs …?!)

That said, YMMV, and it’s possible that alternative teaching methods do make this an uncomfortable discussion.

19 Likes
#16

Separate thought, separate comment: I agree with earlier posters that traverse is massively underrated among beginners as a source of power, probably because (from their perspective) it is an unholy union of control flow management and data transformation. Despite being the same function, mapM (and forM) are easier to grok and using traverse as a generalisation is a very helpful pedagogic way of connecting the theory of typeclasses to real-world programming.

3 Likes
#17

Thank you for reporting from the trenches. That’s … counter-intuitive. Do you teach deeply nested data structures with Prelude types mixed with custom types? Do you guide students away from holding everything inside Lists?

How do you explain the exception empty structure message; or how even a (allegedly) strongly typed language can produce such a run-time error for an out-of-the-box method applied to an out-of-the-box data item?

(I get it that the students you’re teaching today long after FTP happened won’t experience the churn that was the cause of major consternation at the time.)

#18

Do you teach deeply nested data structures with Prelude types mixed with custom types?

A RoseTree a would qualify, presumably? In which case yes.

Do you guide students away from holding everything inside Lists?

On the contrary, we use lists all the time, but the first time they encounter fold[*] is when the Foldable type class is introduced, so we never discuss the possibility that a monomorphic version existed.

How do you explain the exception empty structure message; or how even a (allegedly) strongly typed language can produce such a run-time error for an out-of-the-box method applied to an out-of-the-box data item?

The notion of partial functions comes up early, since students need to get out of the mindset that functions can fail. read, head, minimum, etc serve as useful points of reference as historic failings in standard library design* that we know better than to introduce these days :slight_smile:

* (I contest that the main issue with such partial functions is naming, and that if they were called unsafeHead etc—and not part of Prelude, but some Prelude.Unsafe or similar—then they would basically be fine)

9 Likes
#19

If something is known to be fundamentally broken, I would expect it to be fixed. Especially when we’re talking about a decade-old decision that is still echoing everywhere across the ecosystem (see both Foldable1 in base-4.18+ and the indexed-traversable package).

This as such belongs to the broader “when is base-5 coming” discussion, a seemingly gargantuan undertaking that both seems impossible (hasn’t been done in 15 years) and inevitable (gotta cleanup some day).

#21

If one point of evidence is not enough, here is Graham Hutton:

GH : Yah, so I mean, I was one of the, I mean the Foldable-Traversable thing is something which I was not very keen on when it was being proposed and voted on. But actually, I mean, since, I was worried it would it would have a negative impact on how I teach Haskell, for example, but actually it didn’t. … But, yeah, I did worry about the Foldable-Traversable stuff, but in practice it’s had essentially zero impact on how I teach Haskell, which is good, because I did worry about that one.

14 Likes
#22

If.

Pretty much every type class has its flaws and would had been designed differently if our past selves had all our current knowledge and experience gathered. Is Foldable somehow outstanding? I have not seen such evidence.

2 Likes