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.

Uh oh!

Add 'foldr1' to the 'Foldable1' typeclass #307

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions