Thank you Atze for a well-written description.
Cheers! :)
I think there might be a couple of typos there?
Sadly, due to the finiteness of life I cannot guarantee perfection in all my communication. However, if you see typos, I would greatly appreciate it if you fix them (it's a wiki). :)
(c, r'') = decomp r x -- rhs s/b: decomp r' x ?? Your "motivation" example is hard to follow without knowing what `decomp` does. (IOW, it is not showing me a motivation ;-)
Woops! Sorry! I messed up the example, i've changed it now to: g :: Rec r -> Rec ("p" ::= String .| r) g r = let r' = f (x := 10 .| r) (c,r'') = (r'.!x, r' .- x) v = if c then "Yes" else "Nope" in p := v .| r''
I'm puzzled by this in the implementation notes 4.2 Records:
"Here we see that a record is actually just a map from string to the sequence of values. Notice that it is a sequence of values and not a single value, because the record may contain duplicate labels."
It sounds like there's an overhead in being able to support duplicate labels (even if I don't want duplicates in my records)? Is there a performance penalty at run-time with extending/prepending and restricting/pretruncating, to keep the invariant re the i-th value?
Well, supposing you have no duplicate labels, then all sequences are of length 1. Hence the overhead is that we have a sequence of length 1 instead of just a value (i.e. one extra reference to follow). This is a very small overhead, and in my opinion is justified by the advantages of allowing duplicate labels. Notice also that (.!) always accesses the head of the sequence, since only the leftmost label is accessible (to access shadowed labels, restrict the record with that label).
Leijen allowed duplicate labels to make a virtue of necessity IMO. There has not been an extensible records proposal before or since for duplicate labels. (TRex certainly didn't do it.) His 'necessity' was ease of implementation. This sequence of values stuff seems to make a more difficult implementation for the sake of providing a 'feature' that nobody's asked for(?)
Well, I think Leijen makes two points: * Duplicate labels are nice and allow shadowing in records, which is good. * Duplicate labels allow us to construct a type system lacking a "lacks" predicate, which makes it simpler. I am mainly interested in the first point, see my example. As I said, whether you want duplicate labels depends on the situation. As another use case for duplicate labels: consider implementing an interpreter for some embedded DSL, and you want to carry the state of the variables in the an extensible record. Declaring a new variable in the embedded language then causes us to extend the record. Since the embedded language allows shadowing (as most languages do), we can simply extend the record, we do not have to jump through hoops to make sure there are no duplicate labels. Once the variable goes out of scope, we remove the label again to bring the old "variable" into scope.
Actually, I think there's more wrong with that line than a typo:
extendUnique :: (..., l :\r ) => ... -- s/b: r :\ l ??
(It's supposed to do renaming with non-duplicate labels?)
Sorry! Another mistake, I've fixed it. It is now as follows: renameUnique :: (KnownSymbol l, KnownSymbol l', r :\ l') => Label l -> Label l' -> Rec r -> Rec (Rename l l' r)
Talking of renaming, how does it go with duplicate labels? The comment on `rename` says it can be expressed using the "above operations" (presumably restrict followed by extend with the new label, as per Gastar&Jones and Leijen).
If that's genuinely equivalent, then rename will 'unhide' any duplicate label. So presumably the implementation must split the HashMap into two keys, rather than changing the label on the existing Seq(?)
Yes, exactly. Renaming is implemented as follows, which is equivalent to
what you said:
rename :: (KnownSymbol l, KnownSymbol l') => Label l -> Label l' ->
Rec r -> Rec (Rename l l' r)
rename l l' r = extend l' (r .! l) (r .- l)
renameUnique :: (KnownSymbol l, KnownSymbol l', r :\ l') => Label l ->
Label l' -> Rec r -> Rec (Rename l l' r)
renameUnique = rename
2013/12/6 AntC
Atze van der Ploeg
writes: (see http://www.haskell.org/haskellwiki/CTRex#Duplicate_labels.2C_and_lacks). I think duplicate labels are nice in some situations and bad in other situations.
Thank you Atze for a well-written description.
I think there might be a couple of typos there?
(c, r'') = decomp r x -- rhs s/b: decomp r' x ??
extendUnique :: (..., l :\r ) => ... -- s/b: r :\ l ??
Your "motivation" example is hard to follow without knowing what `decomp` does. (IOW, it is not showing me a motivation ;-)
I'm puzzled by this in the implementation notes 4.2 Records: "Here we see that a record is actually just a map from string to the sequence of values. Notice that it is a sequence of values and not a single value, because the record may contain duplicate labels."
It sounds like there's an overhead in being able to support duplicate labels (even if I don't want duplicates in my records)? Is there a performance penalty at run-time with extending/prepending and restricting/pretruncating, to keep the invariant re the i-th value?
Leijen allowed duplicate labels to make a virtue of necessity IMO. There has not been an extensible records proposal before or since for duplicate labels. (TRex certainly didn't do it.) His 'necessity' was ease of implementation. This sequence of values stuff seems to make a more difficult implementation for the sake of providing a 'feature' that nobody's asked for(?)
There's one 'advanced feature' of extensible records that I'd be interested in: merging records by label, as is done for 'Natural Join'.
a row with labels {x, y, z} merge labels {y, z, w} returns a Maybe row with {x, y, z, w} providing the types paired with y and z are the same and the values are the same (otherwise return Nothing)
It's absolutely essential _not_ to duplicate labels in this case.
AntC
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe