Unfoldable1

[matthewleon]

As a counterpart to Foldable1, I believe an Unfoldable1 makes sense.

[garyb]

I'm not too sure what the signature for this would be, it's something I've considered before too. Closest thing I thought of is it'd be like the reverse of a fold, where you pass a "zero element" in along with the function that actually unfolds.

[garyb]

Actually, I guess the simplest way would be to just turn the Tuple and Maybe inside out a bit:

class Unfoldable1 t where
  unfoldr1 :: forall a b. (b -> Tuple a (Maybe b)) -> b -> t a

So the step function has to always return a value, and just the next step becomes optional.

The other thing I mentioned on Slack:

class Unfoldable1 t where
  unfoldr1 :: forall a b c. (b -> Tuple a c) -> (c -> Maybe (Tuple a c)) -> b -> t a

Also works and potentially gives us a little more flexibility both in writing more efficient unfolds (when the thing unfolded is like x :| xs, as we won't be required to reconstruct c as being head xs :| tail xs for the next step) and also allows this:

instance unfoldable1NonEmpty :: Unfoldable f => Unfoldable1 (NonEmpty f) where
  unfoldr1 f g b = case f b of Tuple a c -> NonEmpty a (unfoldr g c)

Which I think is impossible with the other definition. The tradeoff being callers now have to provide two step functions rather than one.

[matthewleon]

What is wrong with the more obvious (to me)?

class Unfoldable1 t where
  unfoldr1 :: forall a b. (b -> Maybe (Tuple a b)) -> b -> a -> t a

instance unfoldable1NonEmpty :: Unfoldable f => Unfoldable1 (NonEmpty f) where
  unfoldr1 f b a = a :| unfoldr f b

[matthewleon]

(presumably this is going to be used to convert among non-empty structures, so I assume that our a, above, should be easily, and algorithmically cheaply, available)

[garyb]

I didn't like that approach as it puts more work on the caller to partially deconstruct the thing that is being unfolded from, rather than that being part of the process of unfolding. You could argue that if we were going to do something with that form, then there's not really a reason for Unfoldable1 to exist at all, since you just need the ability to abstract over creating something non-empty instead:

class NonEmpty t where
  mkNonEmpty :: forall f a. Foldable f => a -> f a -> t a

[garyb]

I have some more thoughts that I'll write up later, but it looks like the turned-inside-out ((b -> Tuple a (Maybe b))) approach is probably the one we want. I've been experimenting!

[matthewleon]

Cool, I too have some thoughts that I'll try to get down later.

[matthewleon]

Also, glad to hear that the "inside-out" is the right way to go about things, as the alternative was at least esthetically a bit displeasing.

[matthewleon]

spitballing here:

module Main where

import Prelude

import Data.Maybe (Maybe(..))
import Data.Tuple (Tuple(..))
import Data.Unfoldable (class Unfoldable, unfoldr, none)
import Data.NonEmpty (NonEmpty, (:|))

class Unfoldable1 t where
  unfoldr1 :: forall a b. (b -> Tuple a (Maybe b)) -> b -> t a

instance unfoldable1NonEmpty :: Unfoldable f => Unfoldable1 (NonEmpty f) where
  unfoldr1 = unfoldr1NonEmpty

unfoldr1NonEmpty
  :: forall a b f
   . Unfoldable f
  => (b -> Tuple a (Maybe b)) -> b -> NonEmpty f a
unfoldr1NonEmpty f b = case f b of
    Tuple a Nothing -> a :| none
    Tuple a (Just b) -> a :| unfoldr g b
      where
        g :: b -> Maybe (Tuple a b)
        g b' = case f b' of
          Tuple a Nothing -> Nothing
          Tuple a (Just b'') -> Just $ Tuple a b''

(Try PureScript is giving me "failed to create gist")

[garyb]

I figured out a sensible NonEmpty instance for this formulation too in the end, using Maybe as a free monoid:

instance unfoldable1NonEmpty :: Unfoldable f => Unfoldable1 (NonEmpty f) where
  unfoldr1 f b =
    case f b of
      Tuple a Nothing -> NonEmpty a none
      Tuple a (Just b') -> NonEmpty a (unfoldr (flip bind go) (Just b'))
    where
      go b' = case f b' of
        Tuple a Nothing -> Just (Tuple a Nothing)
        Tuple a (Just b'') -> Just (Tuple a (Just b''))

The reason I ended up preferring this version is that it admits reasonable instances for both NEL and Cofree:

instance unfoldable1Cofree :: Alternative f => Unfoldable1 (Cofree f) where
  unfoldr1 f = buildCofree \b -> maybe empty pure <$> f b

The other versions I tried had problems with because either the Cofree was impossible, or one or both of the instances behaved strangely (missing elements, reordering things).

... Oh, I see you just posted, lemme read that before continuing 😉

[garyb]

The version of unfoldr1NonEmpty you provide there suffers from one of the problems I encountered: it will drop an element (the Tuple a Nothing -> Nothing case in g loses that a entirely).

[matthewleon]

Ah, I have another one coming shortly that resolves that. I'll compare to yours.

[matthewleon]

This should result in no dropped elems:

unfoldr1NonEmpty
  :: forall a b f
   . Unfoldable f
  => (b -> Tuple a (Maybe b)) -> b -> NonEmpty f a
unfoldr1NonEmpty f b = case f b of Tuple a mb -> a :| unfoldr g mb
      where
        g :: Maybe b -> Maybe (Tuple a (Maybe b))
        g Nothing = Nothing
        g (Just b') = Just $ f b'

[matthewleon]

Or, even simpler:

unfoldr1NonEmpty
  :: forall a b f
   . Unfoldable f
  => (b -> Tuple a (Maybe b)) -> b -> NonEmpty f a
unfoldr1NonEmpty f b = case f b of Tuple a mb -> a :| unfoldr (map f) mb

[matthewleon]

Golfing here, apologies for the noise, but here is a terser form:

unfoldr1NonEmpty f b = uncurry (:|) $ unfoldr (map f) <$> f b

[garyb]

Hmm, unfortunately I lost a bunch of my workings attempting to show the pitfalls of the various other definitions... but anyway, instead of pointing out the problems with them, I have another reason to like unfoldr1 :: forall a b. (b -> Tuple a (Maybe b)) -> b -> t a - the function you pass in is essentially uncons if you're refolding from one structure to another ("there's always an extractable value + here's the remainder of the non-empty structure / there is no more structure to unfold").

Unfortunately it's not actually uncons for NEL as it has a { head :: a, tail :: List a } result, but close enough 😄, they're isomorphic at least.

The NonEmpty instance is nice 👍I think I just got too zoned in on whatever I was trying plus going through all kinds of permutations 😄

More golf:

unfoldr1NonEmpty f = uncurry (:|) <<< map (unfoldr <$> f) <<< f

😆

[matthewleon]

Well, looks like we ended up basically at the same result through our golf. I actually rejected the point-free form in the end, but I could go either way.

This is good! You going to do a PR?

[garyb]

Yup, I'll put one together now. I think this library will just have the class and the instances will go elsewhere afterwards.

[matthewleon]

I think this library will just have the class and the instances will go elsewhere afterwards.

Yes, I think that works given the dependency graph. Happy to start throwing some PRs around the other libs.