Would someone explain this code to me?
I'm reading Chris Okasaki's "Purely Functional Data Structures", and some of his Haskell is confusing me. He defines the type Color and RedBlackSet as: data Color = R | B data RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a) and then later he defines a function insertSet: insertSet x s = T B a y b where ins E = T R E x E ... T _ a y b = ins s What I don't understand is his use of the "T" constructor, both at insertSet x s = T B a y b and in the where statement: T _ a y b = ins s Is "T" being redefined, so the "T" called in the first line is a new function that happens to be called "T" which is defined in the where statement? If that was the case, I would expect this to work: insertSet x s = foo B a y b where ins E = foo R E x E ... foo _ a y b = ins s but it does not. If anyone can explain what's going on here, I'd appreciate it. Thank you! Justin
"Justin Bailey"
I'm reading Chris Okasaki's "Purely Functional Data Structures", and some of his Haskell is confusing me. He defines the type Color and RedBlackSet as:
data Color = R | B data RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a)
and then later he defines a function insertSet:
insertSet x s = T B a y b where ins E = T R E x E ... T _ a y b = ins s
What I don't understand is his use of the "T" constructor, both at
insertSet x s = T B a y b
Here it creates a new RedBlackSet
and in the where statement:
T _ a y b = ins s
Here it's a pattern match. So if ins s returns (T x a' y' b'), then a = a'; y = y'; b = b' are used in the expresion covered by the where clause. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
On 06 Dec 2006 19:33:51 +0000, Jón Fairbairn
and in the where statement:
T _ a y b = ins s
Here it's a pattern match. So if ins s returns (T x a' y' b'), then a = a'; y = y'; b = b' are used in the expresion covered by the where clause.
Great, thanks for clearing that up. Sometimes Haskell is a bit too concise! Justin
What I don't understand is his use of the "T" constructor, both at
insertSet x s = T B a y b
Here it creates a new RedBlackSet
and in the where statement:
T _ a y b = ins s
Here it's a pattern match. So if ins s returns (T x a' y' b'), then a = a'; y = y'; b = b' are used in the expresion covered by the where clause.
If you're wondering how the compiler tells the difference, have a look at section 2.4 of the Haskell 98 Report (Identifiers and Operators). Roughly, an identifier beginning with a lowercase letter or underscore must be a variable identifier, while an identifier beginning with an uppercase letter must be a constructor identifier. In other words, the second example above cannot be the definition of a function called "T", because "T" cannot be the name of a function.
Justin Bailey wrote:
I'm reading Chris Okasaki's "Purely Functional Data Structures", and some of his Haskell is confusing me. He defines the type Color and RedBlackSet as:
data Color = R | B data RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a)
and then later he defines a function insertSet:
insertSet x s = T B a y b where ins E = T R E x E ... T _ a y b = ins s
What I don't understand is his use of the "T" constructor, both at
insertSet x s = T B a y b
and in the where statement:
T _ a y b = ins s
...
If anyone can explain what's going on here, I'd appreciate it. Thank you!
If you ask correctly GHC will explain for you, with utmost verbosity. It would be a lot more productive for you to look over the Haskell Report and ask questions, but I had more fun working out this approach. So, shall we continue this long and useless but hopefully interesting journey? To turn a module into a program that dumps the AST for the definitions in that module, Replace module *Name* where *imports* *definitions* with {-# OPTIONS -fth #-} module Main where *imports* import Language.Haskell.TH main = do {print =<< runQ [d| *definitions |]} I can wrap up your example like this {-# OPTIONS -fth #-} module Main where import Language.Haskell.TH main = do {print =<< runQ [d| data Color = R | B data RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a) insertSet x s = T B a y b where ins E = T R E x E T _ a y b = ins s |]} Build like this ~$ ghc --make ExplainExample and run to get this ~$ ./ExplainExample [DataD [] Color [] [NormalC R [],NormalC B []] [],DataD [] RedBlackSet [a_0] [NormalC E [],NormalC T [(NotStrict,ConT Color),(NotStrict,AppT (ConT RedBlackSet) (VarT a_0)),(NotStrict,VarT a_0),(NotStrict,AppT (ConT RedBlackSet) (VarT a_0))]] [],FunD insertSet [Clause [VarP x_1,VarP s_2] (NormalB (AppE (AppE (AppE (AppE (ConE T) (ConE B)) (VarE a_4)) (VarE y_5)) (VarE b_6))) [FunD ins_3 [Clause [ConP E []] (NormalB (AppE (AppE (AppE (AppE (ConE T) (ConE R)) (ConE E)) (VarE x_1)) (ConE E))) []],ValD (ConP T [WildP,VarP a_4,VarP y_5,VarP b_6]) (NormalB (AppE (VarE ins_3) (VarE s_2))) []]]] This is very similar -ddump-parsed GHC flag, except that pretty prints the AST back into normal Haskell syntax, losing all the unambiguous labels. If there was some way to get the AST printed with reasonable newlines and indentation, you might actually be able to match this back to your syntax. Maybe combining Data.Generics with some pretty printer library could do that easily, but that's a story for another time. Supposing you could match this back to your syntax, you would find that "ins E = T B a y b" became FunD ins_3 [Clause [ConP E []] (NormalB (AppE (AppE (AppE (AppE (ConE T) (ConE R)) (ConE E)) (VarE x_1)) (ConE E))) []] and "T _ a y b = ins s" became ValD (ConP T [WildP,VarP a_4,VarP y_5,VarP b_6]) (NormalB (AppE (VarE ins_3) (VarE s_2))) [] Matching these back to the grammar in the Haskell Report (the docs for Language.Haskell.TH.Syntax should really include references) would presumably tell you something about how the expression parsed. Brandon
participants (4)
-
Brandon Moore -
Justin Bailey -
Jón Fairbairn -
Matthew Brecknell