Attempt at a heterogeneous fold to an Either

Help
#1

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
 [NoInstanceFound]

Has anyone achieved something like this?

Thanks in advance.

#2

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
#3

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
#4

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
#5

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.

#6

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') =>
  FoldingWithIndex
    FilterFields
    (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