<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"><base href="x-msg://2548/"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Hi Mark,</div><div><br></div><div>Permit me to take a stab from the beginning.</div><br><div><div>On Jan 13, 2015, at 7:39 AM, "Nicholls, Mark" <<a href="mailto:nicholls.mark@vimn.com">nicholls.mark@vimn.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Full code here…<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><a href="https://github.com/goldfirere/nyc-hug-oct2014/blob/master/Equality.hs" style="color: purple; text-decoration: underline; ">https://github.com/goldfirere/nyc-hug-oct2014/blob/master/Equality.hs</a><o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div></div></div></blockquote><div><br></div><div>First off, I should point out that Data.Type.Equality, while indeed served at the address above, is now a standard library. The code in that repo is identical to the version that ships with GHC 7.8.</div><br><blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Lets start at the beginning…<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">data a :~: b where<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Refl :: a :~: a<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Looks reasonable….” a :~: b” is inhabited by 1 value…of type “a :~: a”</span></div></div></div></blockquote><div><br></div><div>This is true, but there's a bit more going on. If, say, we learn that the type `foo :~: bar` is indeed inhabited by `Refl`, then we know that `foo` and `bar` are the same types. That is</div><div><br></div><div>> baz :: foo :~: bar -> ...</div><div>> baz evidence = case evidence of</div><div>>   Refl -> -- here, we may assume that `foo` and `bar` are fully identical</div><div><br></div><div>Conversely, whenever we *use* `Refl` in an expression, we must know that the two types being related are indeed equal.</div><div><br></div><blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">sym :: (a :~: b) -> (b :~: a)<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">sym Refl = Refl<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">hmmm… (a :~: b) implies that a is b<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">so (b :~: a)<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">brilliant</span></div></div></div></blockquote><div><br></div><div>Yes. After pattern-matching on `Refl`, GHC learns that `a` is identical to `b`. Thus, when we use `Refl` on the right-hand side, we know `b` is the same as `a`, and thus the use of `Refl` type checks.</div><br><blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">-- | Transitivity of equality<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">trans :: (a :~: b) -> (b :~: c) -> (a :~: c)<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">trans Refl Refl = Refl<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">-- | Type-safe cast, using propositional equality<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">castWith :: (a :~: b) -> a -> b<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">castWith Refl x = x<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">fine….<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">But….<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">-- | Generalized form of type-safe cast using propositional equality<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">gcastWith :: (a :~: b) -> ((a ~ b) => r) -> r<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -18pt; "><span style="font-size: 11pt; font-family: Wingdings; color: rgb(31, 73, 125); "><span>Ø<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman'; "> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">gcastWith Refl x = x<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">I don’t even understand the signature<o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">What does “~” mean…(it’s something that comes out in error messages when my types are all messed up)….and then there’s a “=>” going on…in the middle of a signature….I know “=>” in the context of “Num a => a -> a -> a”</span></div></div></div></div></blockquote><div><br></div><div>While the comments I've seen about `~` are quite true, I think there's a simpler way to explain it. `~` is simply equality on types. The constraint `a ~ b` means that `a` is the same type as `b`. We could have spelled it `=` if that weren't used elsewhere. Before `~` was added to GHC, it might have been implemented like this:</div><div><br></div><div>> class Equals a b | a -> b, b -> a</div><div>> instance Equals x x</div><div>> -- no other instances!</div><div><br></div><div>The proper `~` works better in type inference than this functional-dependency approach, but perhaps rewriting `~` in terms of functional dependencies is illuminating.</div><div><br></div><div>When a constraint `a ~ b` is in the context, then GHC assumes the types are the same, and freely rewrites one to the other.</div><div><br></div><div>The type `(a ~ b) => r` above is a higher-rank type, which is why it may look strange to you. Let's skip the precise definition of "higher-rank" for now. In practical terms: let's say you write `gcastWith proof x` in your program. By the type signature of `gcastWith`, GHC knows that `proof` must have type `a :~: b` for some `a` and `b`. It further knows that `x` has the type `(a ~ b) => r`, for some `r`, but the same `a` and `b`. Of course, if a Haskell expression as a type `constraint => stuff`, then GHC can assume `constraint` when type-checking the expression. The same holds here: GHC assumes `a ~ b` (that is, `a` and `b` are identical) when type-checking the expression `x`. Perhaps, somewhere deep inside `x`, you pass a variable of type `a` to a function expecting a `b` -- that's just fine, because `a` and `b` are the same.</div><div><br></div><div>The `r` type variable in the type of `gcastWith` is the type of the result. It's the type you would naively give to `x`, but without a particular assumption that `a` and `b` are the same.</div><br><blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">What would a value of type “((a ~ b) => r)” look like?</span></div></div></div></div></blockquote><div><br></div><div>It looks just like a value of type `r`. Except that GHC has an extra assumption during type-checking. Contrast this to, say,</div><div><br></div><div>> min :: Ord a => a -> a -> a</div><div>> min = \x y -> if x < y then x else y</div><div><br></div><div>What does a value of `Ord a => a -> a -> a` look like? Identically to a value of type `a -> a -> a`, except with an extra assumption. This is just like the type `(a ~ b) => r`, just less exotic-looking.</div><div><br></div>As for singleton types and dependent types: they're great fun, but I don't think you need to go anywhere near there to understand this module. (Other modules in that repo, on the other hand, get scarier...)<blockquote type="cite"><div lang="EN-GB" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0cm 0cm 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div></div></div></blockquote></div><div><br></div><div>I hope this helps!</div><div>Richard</div></body></html>