Hacker News Reader

Comment by twiss | Hacker News Reader

I think part (but not all) of the blame in this case should fall to `length` and `.iter().count()` doing something rather different for a list and an Option/Maybe type. Does taking the length/iter of the latter really make sense? Or should one have to do `option.is_some() as usize` instead, if that's really what you want?

If the same method always did the same for all types that implement it, this problem wouldn't occur. (That being said, I understand that that might be too much to ask for / can't always be avoided.)

View on HN

But you see, this behavior is the result of uniformly doing the same thing. You're asking for it to have special cases.

The signature "length :: Foldable f => f a -> Int" is pretty specific. The polymorphism is parametric over `a' and ad-hoc over `f'. It has to select its behavior based only on the "container" type, rather than the "element" type. (The quoted terms are sloppy, but better for intuition than talking about deconstructing curried generative type constructor application.)

Here's the thing about that. If your type is (Maybe (List Foo)), the `f' variable (container type) gets matched with `Maybe'. The `a' variable (element type) gets matched with (List Foo). So the fact that there's a list involved gets thrown away during instance resolution.

And that's a good thing, because it lets you reason about your code's behavior uniformly. Just seeing the type of `length' is enough to tell you it has to work this way. Any attempt to work another way would fail to type-check.

Ultimately I think I slightly agree with the original post, but I think it oversells the issue. Using ad-hoc polymorphism inside a definition that doesn't expose that polymorphism externally does allow a few more more incorrect implementations. That is some form of erosion of type safety, but a very minor one compared to what ad-hoc polymorphism allows you to recover in safety when writing code that's useful across many types.

> The signature "length :: Foldable f => f a -> Int" is pretty specific.

That may be, but it isn't the best way to describe the type of `length Maybe`, which behaves more like `f a -> Bool`, since it can only return 0 or 1.

> You're asking for it to have special cases.

Not really, I'm just questioning whether the `Maybe` type should implement `length`. Does it make sense to use an int to describe whether it has a value? Does it make sense to call that int its "length"? I would argue: sort of, but there are better names for it, such as `boolToInt . isJust`.

> Not really, I'm just questioning whether the `Maybe` type should implement `length`.

In this case no effort is made to make `Maybe` implement `length` specifically other than making it implement `Foldable`.

    ghci> :i Maybe
    ...
    instance Foldable Maybe -- Defined in ‘Data.Foldable’
    ...

and `length` is a method of the `Foldable` typeclass.

    ghci> :i Foldable
    ...
    length :: t a -> Int
    ...

https://hackage.haskell.org/package/base-4.18.0.0/docs/Prelu...

length implementation for `Maybe`

https://hackage.haskell.org/package/base-4.18.0.0/docs/src/D...

edit - accidentally submitted while part way through editing.

OK, but the question remains, does it make sense for `Maybe` to implement `Foldable`?

The second link says:

> The Foldable class generalises some common "Data.List" functions to structures that can be reduced to a summary value one element at a time.

does it make sense for this to apply to `Maybe`? I guess technically, sort of, but I think it's not a perfect fit. Perhaps there might be some use cases for it, but I'd argue it also carries some risks, as demonstrated in the posted article.

> to structures that can be reduced to a summary value one element at a time.

This is the key part in my mind. Or elsewhere in the documentation:

> Class of data structures that can be folded to a summary value.

https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-...

Foldable is the generalization, in the mathematical sense of the word, of some list functions, but it is not just the list functions. Generalizing something and applying to other structures sometimes results in unintuitive behavior, but is mathematically correct.

`Maybe` makes mathematical sense with foldable. A function with the type that `length` has for Foldable `Foldable f => f a -> Int` makes sense as well. The number of items in a list or a tree, or various other structures makes sense for 'data structures that can be folded to a summary value'.

The design decision I think is whether or not you call `Foldable f => f a -> Int` in Foldable `length` or something else. Since you have `length` for list structures already and `Foldable f => f a -> Int` is `length` for lists you can call it `length` instead of having two functions `length :: [a] -> Int` and lets say `foldCount :: Foldable f => f a -> Int` that both do the same things for lists.

I am pretty sure a discussion on this decision popped up, both in mailing lists and r/haskell, when they made the switch from `length :: [a] -> Int` to `length :: Foldable f => f a -> Int` in the haskell prelude. I did not follow it closely though both reduction in function count, pedagogical arguments and more came up.

edit - The proposal was the FTP proposal if you want to google those conversations.

Some links to start with

FAQ:

https://wiki.haskell.org/Foldable_Traversable_In_Prelude

random reddit conversation on r/haskell that popped up on a google search:

https://www.reddit.com/r/haskell/comments/3okick/foldable_fo...

You're sort of asking the wrong question. The choice wasn't whether Maybe should implement length. Instead, there were two independent choices: should Maybe implement Foldable, and should length be implemented in terms of Foldable?

For the first, the answer is absolutely yes. You really want things like traverse and sequence to work with Maybe, and that requires Maybe to implement Foldable (on the way to Traversable.) It's incredibly useful to be able to treat Maybe as just another container type.

Whether length should be in terms of Foldable, by contrast, is a much more debatable question. On one hand, it means a lot of unexpected things can have length called on them. (length (3,4)) evaluates to 1, for instance; that's just almost never useful, despite being completely logical. On the other hand, it's really awkward to need a different function to get the size of every container type. Especially when you can write a length function using just Foldable. And I think that's what led to that decision - if the standard library doesn't provide that definition, a whole bunch of other libraries will.

I'm still not sure about that decision. It's got some weird corner cases. There are some cases where it allows bugs, as the article points out. But at the same time, I have written code that is happy to use that degree of polymorphism, and does so safely because it allows the caller to choose the concrete type.

Maybe the real problem isn't the existence of those instances. Maybe the underlying issue is that you can use ad-hoc polymorphism at concrete types without knowing what those concrete types are. The article did touch on that aspect in its final paragraph, when it mentioned monomorphizing length at the call site. But even this feels like it could easily introduce more pain that it solves.

I've spent more time here talking about the potential issue than I ever have spent dealing with it in real software. Maybe it's just not that big of a deal.

It’s useful for Option to be iterable so that it works with things like .flat_map(), and it’s useful to be able to count from an arbitrary iterable.

.iter().count() is a contrived way to find the length of a Vec though, since .len() is clearer and faster.

Reply on news.ycombinator.com