Attempt at a heterogeneous fold to an Either

I am trying to do a heterogeneous fold over a record with values having Eithers. The rows of the record represent input values in a form. They are either Right indicating a successfully captured value or Left indicating error. So {field1: Right "good"} or {field1: Left e}. I wish to fold this structure, and flatten it into a record of Right { field1: "good", ... } or a Left e, if there is an error in any row encountered during the fold.

Maybe it is easier for you to read my attempt at the instance:

instance foldRight ::
  (IsSymbol sym
  , Row.Lacks sym r
  , Row.Cons sym b r r') =>
  FoldingWithIndex FilterFields (Proxy sym) (Either a { | r }) (Either a b) (Either a { | r' })  where
  foldingWithIndex FilterFields k (Right rec) (Right b) = Right (Record.insert k b rec)
  foldingWithIndex FilterFields k _ (Left a) = Left a
  foldingWithIndex FilterFields k (Left a) (Right _) = Left a

foldRecord ::
  forall a r1 r2.
  HFoldlWithIndex FilterFields (Either a {}) (Either a { |r1 }) (Either a { | r2}) =>
  Either a {|r1} ->
  Either a {|r2}
foldRecord r = hfoldlWithIndex FilterFields ((Right {}) :: Either a {}) r

Unfortunately, the compiler groans with:

No type class instance was found for

    Heterogeneous.Folding.HFoldlWithIndex FilterFields
                                          (Either a4 (Record ()))
                                          (Either a5 (Record r16))
                                          (Either a5 (Record r27))

while applying a function hfoldlWithIndex
  of type HFoldlWithIndex t0 t1 t2 t3 => t0 -> t1 -> t2 -> t3
  to argument FilterFields
while inferring the type of hfoldlWithIndex FilterFields
in value declaration foldRecord

where a4 is a rigid type variable
        bound at (line 0, column 0 - line 0, column 0)
      r16 is a rigid type variable
        bound at (line 0, column 0 - line 0, column 0)
      r27 is a rigid type variable
        bound at (line 0, column 0 - line 0, column 0)
      a5 is a rigid type variable
        bound at (line 0, column 0 - line 0, column 0)
      t2 is an unknown type
      t3 is an unknown type
      t0 is an unknown type
      t1 is an unknown type

Has anyone achieved something like this?

Thanks in advance.

I have written a little helper library on top of Nate’s heterogeneous library to make that easier and also recurse the record, you can have a look at it here.

1 Like

Just a thought, but I’m surprised you’re not using Validation, so that you can accumulate all errors rather than just stopping at the first one.

1 Like

There’s also the sequenceRecord function, though I think it only works if every field of the record is an Either (or V), and not a mix like the solution @sigma-andex posted

1 Like

Thanks all. To be clear, I do have some motivation, however masochistic, to understand the resolution of types in a non-trivial class like this, so I am enjoying playing around with this example a bit. I see @sigma-andex’s library approaches the ‘sequencing’ differently by accumulating as an unapplied function at each fold iteration. I could adapt this idea, or just use the lib I suppose, it is exactly what I want to do and more. Interestingly my code works if I change my Left type to unit, so it seems to be something to do with the resolution of the type under the Left.

@JordanMartinez I think I could quite easily make the error type under the Left monoidal, if I could get my toy example working that is. Thanks for the link nonetheless, that is an interesting and full featured approach.

For anyone who cares about this, the problem was with how I propagated the initial ‘base case’ error type, where by error type I mean the type under the Left, through to the final error type. Put simply, I needed a separate type variable to model the final error versus the initial error. As in HFoldlWithIndex FilterFields (Either a {}) (Either b { |r1 }) (Either b { | r2}). However this made things awkward and clunky, and the original foldRight instance I wrote above, if you squint, is basically rewriting the applicative instance for Either. So taking some inspiration from @sigma-andex’s lib I just hid the Either a type constructor under a more general Applicative f and it all worked nicely.

Working version.

data FilterFields = FilterFields

instance foldRight ::
  (IsSymbol sym
  , Applicative f
  , Row.Lacks sym r
  , Row.Cons sym b r r') =>
    (Proxy sym)
    (f { | r })
    (f b)
    (f { | r' }) where
  foldingWithIndex FilterFields k fr fb = (Record.insert k) <$> fb <*> fr

foldRecord ::
  forall r r1 rl f.
  Applicative f =>
  RL.RowToList r rl =>
  HFoldlWithIndex FilterFields (f {}) { | r } (f { | r1}) =>
  { | r } ->
  f { | r1}
foldRecord r = hfoldlWithIndex FilterFields (pure {} :: f {}) r

Much more pleasing to the eye! I suppose FilterFields is not really a relevant name anymore, but you get the idea.

1 Like