Alternative approaches

[pete-murphy]

It's been pointed out that Fold is isomorphic to a Moore machine, and there's a purescript-folds package that doesn't use the existential type. According to Nate Faubion:

Note that Fold can admit more fusion simply because you can step multiple times without calling (x -> b), and maps can be fused. It essentially embeds coyoneda. Moore requires you to apply it at every step.

I still haven't digested that—does it mean the encoding using the existential type (this one as opposed to that in purescript-folds) is more efficient somehow?

Further reading:
Kmett on Moore & transducers: https://www.schoolofhaskell.com/user/edwardk/moore/for-less

Alternative fold libraries (since I don't know where else to track these):
https://github.com/metrix-ai/deferred-folds
https://github.com/effectfully/prefolds
https://github.com/ekmett/folds

[pete-murphy]

xgrommx
—
10/21/2022 11:03 AM
@pete (he/him) by the way this is just Moore's machine
xgrommx
—
10/21/2022 11:16 AM
@pete (he/him)

data Moore a b = Moore b (a -> Moore a b) -- ~ Fold a b
data Cofree f a = Cofree a (f (Cofree f a))

-- Moore a b ~ Cofree ((->) a) b
-- Nu f = exists x. Tuple (x -> f x) x
-- Cofree f a ~ Nu (Compose (Tuple a) f)
-- Cofree f a ~ exists x. Tuple (x -> Tuple a (f x)) x

-- Moore a b ~ Cofree ((->) a) b ~ exists x. Tuple (Tuple (x -> b) (x -> a -> x)) x
-- Moore a b ~ Cofree ((->) a) b ~ exists x. Tuple (Tuple (x -> a -> x) x) (x -> b)

data FoldF a b x = FoldF (x -> a -> x) x (x -> b)
type Fold a b = Exists (FoldF a b)

-- Moore a b ~ Fold a b

natefaubion
—
10/21/2022 12:46 PM
Note that Fold can admit more fusion simply because you can step multiple times without calling (x -> b), and maps can be fused. It essentially embeds coyoneda. Moore requires you to apply it at every step.