hfoldlWithIndex on homogeneous Record

I’m using purescript-heterogeneous to show the contents of a homogeneous records of strings.

myRec = { a: "x", b: "y" }
showRec1 myRec == ",x,y"
showRec3 myRec == ",a=x,b=y"

I’m attempting write a showRec2 function that produces the same output as showRec3 (with labels), but written in the simpler style of showRec1 to avoid needing a ShowStringProps instance.

Do I just have a minor typo in showRec2, or are custom instances required to use hfoldlWithIndex?

module Main where

import Prelude
import Effect (Effect)
import Effect.Console (log)
import Heterogeneous.Folding (class FoldingWithIndex, class HFoldl, class HFoldlWithIndex, hfoldl, hfoldlWithIndex)
import Data.Symbol (class IsSymbol, SProxy, reflectSymbol)

myRec :: { a :: String, b :: String }
myRec = { a: "x", b: "y" }

showRec1 :: forall r. HFoldl (String -> String -> String) String r String => r -> String
showRec1 r =
    f :: String -> String -> String
    f acc val = acc <> "," <> val
    hfoldl f "" r

showRec2 :: forall sym r. IsSymbol sym => HFoldlWithIndex (SProxy sym -> String -> String -> String) String r String => r -> String
showRec2 r =
    f :: forall sym. IsSymbol sym => SProxy sym -> String -> String -> String
    f sym acc val = acc <> "," <> reflectSymbol sym <> "=" <> val
    hfoldlWithIndex f "" r

data ShowStringProps
  = ShowStringProps

instance showStringProps :: (IsSymbol sym) => FoldingWithIndex ShowStringProps (SProxy sym) String String String where
  foldingWithIndex ShowStringProps sym acc val = acc <> "," <> reflectSymbol sym <> "=" <> val

showRec3 :: forall r. HFoldlWithIndex ShowStringProps String r String => r -> String
showRec3 r = hfoldlWithIndex ShowStringProps "" r

main :: Effect Unit
main = do
  log $ showRec1 myRec
  log $ showRec2 myRec
  log $ showRec3 myRec

Here’s my compilation error:

Error found:
in module Main
at src/Main.purs:26:5 - 26:22 (line 26, column 5 - line 26, column 22)

  No type class instance was found for
    Heterogeneous.Folding.HFoldlWithIndex (SProxy t4 -> String -> String -> String)
  The instance head contains unknown type variables. Consider adding a type annotation.

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

where r5 is a rigid type variable

Custom instances are always required for anything that is polymorphic. hfoldlWithIndex is going to take an SProxy which has no runtime information. It’s equivalent to unit, so anything interesting will be based on type-level information, and thus require constraint-based polymorphism.

1 Like

It is not directly relevant to the heterogeneous package (which I find often really useful) and the question :slight_smile: but if you want to quickly hack on some homogeneous record you can find Foreign.Object.fromHomogeneous a bit easier to use. Maybe Foreign.Object sounds scary a bit but it is just a plain JS object underneath and it can be easily turn into Data.Map String a with Data.Map.fromFoldableWithIndex or folded or traversed in general (like a Map String a… it was even called StrMap in the past):

module Main where

import Prelude

import Data.Foldable (intercalate)
import Data.FunctorWithIndex (mapWithIndex)
import Effect (Effect)
import Effect.Class.Console (log)
import Foreign.Object (fromHomogeneous) as Foreign.Object

showRec3 = intercalate ", " <<< mapWithIndex (\label value → label <> "=" <> value) <<< Foreign.Object.fromHomogeneous

main ∷ Effect Unit
main = do
  log $ showRec3 { one: "jeden", two: "dwa", three: "trzy" }
$ spago run
[info] Build succeeded.
one=jeden, two=dwa, three=trzy

Great example.
intercalate is a nice find too. I really need to take a closer look at the Foldable docs.

Shameless plug: https://github.com/JordanMartinez/purescript-jordans-reference/tree/latestRelease/21-Hello-World/04-Collections-and-Loops/src

1 Like

@milesfrain after a second thought I think that we can do better than simply fall back to unstructured Foreing.Object as I have proposed above.

When we use Foreign.Object.fromHomogeneous we loose the information about record structure but gain convenient instances like Functor, Foldable, Traversable etc. On the other hand when we try to use generic RowList based approach (from libraries like heterogeneous or homogeneneous-record) we keep the info about structure but it comes with a quite heavy typelevel machinery regarding internal implentation.

It seems that with a minimal effort we can use nice, efficient and simple Foreign.Object approach but also preserve the info about the Record row structure on the type level so we would be able to “go back” to the properly typed record easily. So let’s consider this type:

newtype Homogeneous (row ∷ # Type) a = Homogeneous (Foreign.Object a)

We can assume that row provides only information about the structure and we can “fill it” with Unit as a placeholder. The parameter a keeps track of the type of values in our homogeneous Record / Object. What we also need is a bunch of derive newtype instance (including foldableWithIndex ;-)) some custom instances and a smart constructor which checks whether an input Record is really a monomorphic one.

Let’s try to define a constructor. Using @natefaubion typelevel-eval machinery we can create a monomorphic row type from another row type quite easily:

type MapRowConst a = ToRow <<< Map (Const a) <<< FromRow

In the above snippet <<< is a typelevel composition operator provided by the lib. All these additional constructors seems to be self explanatory and compose so nicely!
But let me read through MapRowConst a declaration. We can think of this type as type level function expression. This function takes some Row type, turns it into RowList then maps Const a which puts type a into every RowList value type slot and turns it back into the resulting Row type.
Every such an expression can be evaluated using Eval constraint (in the below snippet we pass to the above mapping row ra and we get ru as a result which is ra filled with Unit in the place of an a type). So here is our final constructor:

  ∷ ∀ a ra ru
  . Row.Homogeneous ra a
  ⇒ Eval (MapRowConst Unit (Row.RProxy ra)) (Row.RProxy ru)
  ⇒ { | ra }
  → Homogeneous ru a
homogeneous = Homogeneous <<< Object.fromHomogeneous

It is worth noting that we also use Row.Homogeneous from the typelevel-prelude which was a really nice addition to this lib by @paulyoung. This constraint checks that a given Row type contains only type a as a value type. We can be sure now that we accept only monomorphic Records.

Inverse transformation is based on the assumption that our invariant from the type level holds on the value level so we can build a record type by filling our “row structure type” (ru parameter - row which was previously filled with Unit) with a and by performing safe unsafeCoerce on the value level:

  ∷ ∀ a ru ra
  ⇒ Eval (MapRowConst a (Row.RProxy ru)) (Row.RProxy ra)
  . Homogeneous ru a
  → { | ra }
toRecord (Homogeneous obj) = unsafeCoerce obj

With this representation we get some instances “for free”:

derive newtype instance functorHomogeneous ∷ Functor (Homogeneous r)
derive newtype instance foldableHomogeneous ∷ Foldable (Homogeneous r)
derive newtype instance foldableWithIndexHomogeneous ∷ FoldableWithIndex String (Homogeneous r)
derive newtype instance traversableHomogeneous ∷ Traversable (Homogeneous r)
derive newtype instance semigroupHomogeneous ∷ Semigroup a ⇒ Semigroup (Homogeneous r a)

So now we are able to do:

main :: Effect Unit
main = do
  logShow $ toRecord $ (_ * 2) <$> homogeneous { a: 1, b: 2, c: 3 }

and get back a record:

[info] Build succeeded.
{ one: 2, three: 6, two: 4 }

The above FoldableWithIndex instance is somewhat weak because on the type level we have full info about labels but provide only a String value as an index to the folding function. I think that we can do better when we introduce and use Variant instead. But this along with "homogeneous Variant" (which has OMG… a Comonad instance!) can be a subject of the next installment if anybody is interested.

Let’s go back for a moment to the topic of instance deriving. We have to be careful using this mechanism and not copy too much. We want only instances which are consistent with the given “row structure”. Given that Monoid is not a good candidate for a newtype deriving in this case. I’m going to spam about this in the next post as well… even if nobody is interested :stuck_out_tongue:

1 Like

Here I have a library stub which uses the above approach: https://github.com/paluh/purescript-homogeneous