Add 'foldr1' to the 'Foldable1' typeclass

[chshersh]

No description provided.

[rektrex]

foldr1 here should behave similar to foldr from the standard prelude, right?

[jgm]

foldr1 from standard Prelude has type (a -> a -> a) -> t a -> a.
The idea is that if it's nonempty structure, you don't need the "starting value" for the fold.

foldr1 from relude has type (a -> b -> b) -> b -> f a -> b. Note the extra parameter. Is this difference in type intended?

[chshersh]

@jgm Removing the default value would be nice indeed. However, it doesn't look trivial to do. I see, that even semigroupoids doesn't provide foldr1, and I don't see from Hoogle any library that provides safe foldr1 with the nice type signature.

[Anton-Latukha]

Yeah, no base case is simple when:

-- base
foldr1 :: (a -> a -> a) -> t a -> a

But remove the base case for:

-- base
foldr  :: (a -> b -> b) -> b -> t a -> b
-- relude
foldr1 :: (a -> b -> b) -> b -> t a -> b 

Is completely another thing.

AFAIK the base cases should not be removed. Everyone expects fold to have a function and then a base case. It is trivial to optimize it & GHC optimizes away that typed Lambda calculus argument order. Base cases are free in provisioning and in code performance. And giving base cases is a good FP practice. Base cases are essential for FP programming, Monoid empty, Nothing, bool, maybe, either, fromMaybe and etc which give Lispy-style (which I adopted), all always give base cases first.

Haskell is non-strict, which means if the base case in the proper place (after constant function arg reuse) - it is free, non-strict language would not arrive into base case if it was not used. It is not deferred the specific case of folds, because acc is an accumulator and so gets compounded if fold does anything, because its semantics is to recursively change the base case, and the structure tail fold operates on changes anyway also on every iteration. The theory is straightforward and holds overboard for all base cases in Haskell.

When to try to remove the base case too hard, the base foldr1 is what comes out as a result, a one-sided non-general fold. and then people have this sort of discussion. To say like in the kindergarten: we see that the base: foldr1 is one being weird here.

[jgm]

I guess that's my question exactly. Why not have the signature

Foldable1 t => (a -> a -> a) -> t a -> a

Foldable1 is for nonempty structures; we have a way to get head and last, so why do we need to specify a base case? This would make foldr1 a drop-in replacement for Prelude's, more or less, instead of something completely different. If you need the flexibility of

(a -> b -> b) -> b -> t a -> b

and don't mind specifying a base case, just use foldr which already looks like this. Obviously there's something I'm missing.

[Anton-Latukha]

Because fold for non-empty structures if to take-out the base case would be in an imaginary world we imagine is:

-- imaginary
(a -> b -> b) -> t a -> b
-- base
(a -> a -> a) -> t a -> a
-- relude
(a -> b -> b) -> b -> t a -> b

If to pick real one - it is the relude one. It is just the same fold, but with NonEmpty power. Because the (a -> a -> a) -> t a -> a is not practical.
It is much more practical to just give base case that is for free and have proper catamorphism.
Then to reduce what was for free to get a partial solution that constricts the implementation.
What is in base just needed another name to not constantly create this discussion.

We actually participate in a years long epic discussion on why that foldr1 was put there, it is a holly war, I used to read about it years ago, even before I learned Haskell properly.

That is why I just decided to submit the note that it is a different implementation.

[jgm]

I don't mean to engage in a holy war, but what confuses me is this.
NonEmpty is already an instance of Foldable, which has the type

foldr :: (a -> b -> b) -> b -> t a -> b

So what exactly is the difference between foldr and foldr1 (with relude's type)?

[Anton-Latukha]

That *1 naming used consistently. foldr1 is Foldable1, which gives what Foldable1 does - gives a guarantee that the structure is empty-safe. While foldr with Foldable does not provide that guarantee and allows non-total unsafe functions.

[jgm]

While foldr with Foldable does not provide that guarantee and allows non-total unsafe functions.

foldr from the Foldable class is perfectly safe for empty structures, isn't it? It's not a partial function. Maybe I'm missing something, but I think you must have meant to be talking about foldr1 from Foldable. Yes, that function is not safe for empty structures. So I would have expected Foldable1 to provide a safe replacement foldr1 that is restricted to nonempty structures but otherwise works like foldr1 from Foldable (and has the same signature). Instead, relude offers a function that has the same signature as foldr from Foldable, and (if I understand correctly) is equivalent to it (within a more limited domain of application) and thus redundant. Wouldn't it be more useful to provide a safe foldr1 with the original signature? That would allow you to do something you can't already do with foldr. I don't see how it helps to give us a function that just does what foldr already does but with a different name.

foldr1 (with the original signature) is useful when there's no default base case, but you want to start with first element in the structure, whatever it happens to be. I've seen cases like this; to achieve safety in these cases, I've just used foldr and a Maybe, but that's a bit awkward and I would have rather had a safe foldr1 (with no base case) that is restricted to nonempty structures.

[Anton-Latukha]

Since foldr is not NonEmpty typesafe, on empty t a the unsafe (a -> b -> b) can run on it. That people think about about unsafe only in terms of the [a] -> a does not mean that magically unsafe (a -> b -> b) does not exist in the scope of t a when it is empty.

[Anton-Latukha]

(within a more limited domain of application) and thus redundant.

This almost does not happen in Haskell, especially by thoughtful authors. In Haskell for "more limited domain of application" people often use words "specialized to", "more powerful", "optimized for". As if used properly when needed, special cases optimize better, for some cases MonadPlus for parsers is more powerful then Alternative, Abelian structure is much more performant then Semigroup, more restrictions, more properties - more implementation optimization possible. The weaker structures in most cases can be used, but frequently they work less efficiently. The best the most understandable example that I've seen is comparing Associative to Associative & Commutative, what is only Associative is strictly one-threaded sequential, the Commutative gives complete parallelism.

[Anton-Latukha]

I would have rather had a safe foldr1 (with no base case) that is restricted to nonempty structures.

There are none such. NonEmpty structures always have the base case, that is what to do for NonEmpty value.

base: foldr1 documentation starts as: "A variant of foldr that has no base case, and thus may only be
applied to non-empty structures.

This function is non-total and will raise a runtime exception if the
structure happens to be empty."

"may only be applied to non-empty structures." which is only said in words, implementation has only "Foldable" constraint - which is an implementation error. If code relies on verbal words said and works only if user turns the proper way to fit the code - that is not user's fault that the code is unsafe and falls.

Non-totality in code is one of the most known banes to avoid almost at all cost in the Haskell.

relude provides safe functions. The first content word in its slogan is safe.

relude: foldr1 abilities includes the (a -> a -> a) while also providing the safety with the base case, and in it catamorphism can be anything: (a -> b -> b) -> b, whenever (a -> a -> a) is very limiting.

[jgm]

Since foldr is not NonEmpty typesafe, on empty t a the unsafe (a -> b -> b) can run on it.

Sorry, I'm just not following. Can you give an example where

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

from Foldable blows up on an empty structure (t a)? It's a totally defined function, is it not? In what sense, exactly, is it unsafe to use on empty structures?