December 2007 - Haskell-Cafe

Fwd: Attempt at defining typeful primary key/foreign key relationships
by Justin Bailey 01 Jan '08

01 Jan '08

Small correction - the extensions listed at the bottom weren't necessary. I had attempted to define a relationship among tables automatically as: instance (HasField fk child, HasField pk parent, HasRelation pk fk) => HasRelation parent child But that was redundant with the signature on relation. Removing it allowed me to remove all extensions except MultiParameterTypeClasses. Justin ---------- Forwarded message ---------- From: Justin Bailey <jgbailey(a)gmail.com> Date: Dec 31, 2007 12:25 PM Subject: Attempt at defining typeful primary key/foreign key relationships To: haskelldb-users(a)lists.sourceforge.net All, As part of my data model, I'd like to say there is a primary key/foreign key relationship between two tables/queries. Right now I only want to do this to capture some extra-query information that I'm using for code generation - I don't intend it to actually affect queries generated, though I'd like to go there eventually. I define a class which says there is a relation: class HasRelation pk fk I define a type which holds relation values: data Relation a pk fk p c = Relation { ... } Relation values can only be constructed by a function with appropriate constraints on it: relation :: (HasRelation pk fk, HasField pk parent, HasField fk child) => Attr pk a -> Attr fk a -> Rel parent -> Rel child -> Relation a pk fk parent child relation primaryKey foreignKey prnt chld = Relation .... As an example, if I have tables Orders and LineItems, both with field order_id, I can establish a relationship by first defining an instance: instance HasRelation Orders.Order_id LineItems.Order_id I can then create a relation value between the two: orders <- table Orders.orders lineItems <- table LineItems.lineItems let r1 = relation Orders.order_id LineItems.order_id orders lineitems Note these types would be defined using DBDirect, so Order_id as a type with one constructor, lineItems has type "Table ...", etc. If I try to define an incorrect relation (wrong fields, fields in the wrong order, etc), then the above will not compile, which is just what I want. If you've read this far, I've not done any type-level programming or even played much with classes and instances before so I'd like to know if the approach makes sense. I took most of my inspiration from the HasField class in the HDBRec module. 1) Could this be simpler? Any obvious deficiencies? 2) I had to enable a number of extensions (though all of these are also enabled by haskelldb) - FlexibleInstances, FlexibleContexts, UndecidableInstances and OverlappingInstances. Should I be worried? 3) It's possible to define relationships among any two types. How can I limit that to 1) attributes with 2) the same type? Would I have to define an Attr typeclass, parallel to the Attr type? Thanks for any and all feedback. Happy New Year! Justin

1 0

Trying to fix space leak
by Ben Challenor 01 Jan '08

01 Jan '08

Hi I'm learning Haskell through writing a compiler. I'm seeing huge memory use in a function which converts the dataflow graph to the form required by Data.Graph. It needs to return a map from dataflow nodes to Vertexs, a map in the other direction, and the list of edges (as Vertex pairs). > total time = 18.78 secs (939 ticks @ 20 ms) > total alloc = 6,616,297,296 bytes (excludes profiling overheads) > > COST CENTRE MODULE %time %alloc > > j Dataflow 87.6 99.9 > graphvizCompile Dataflow 6.4 0.0 > f Dataflow 2.9 0.0 > con2tag_DFReal# Representation 2.1 0.0 I assume the allocation is being garbage-collected pretty quickly, because a) 6,616,297,296 bytes is stupid (!) and b) Process Explorer informs me that the peak private bytes of the program is not more than a couple of MB. The offending code looks like this: > -- (next Vertex available for use, edges so far, map so far, map so far) > type DependencyEdgesAcc = (Vertex, [Edge], Map.Map DFNode Vertex, Map.Map Vertex DFNode) > > -- Process a list of DFNodes in the same context. > dependencyEdges :: DependencyEdgesAcc -> [DFNode] -> DependencyEdgesAcc > dependencyEdges acc [] = {-# SCC "a" #-} acc > dependencyEdges acc@(_, _, mnv1, _) (n:ns) = > -- Check whether this node has been done before. > {-# SCC "j" #-} case {-# SCC "i" #-} Map.lookup n mnv1 of > Just _ -> {-# SCC "b" #-} dependencyEdges acc ns > Nothing -> > -- Find the list of dependencies. > let ndeps = {-# SCC "c" #-} nodeDependencies n in > -- Process them first. > let (v2, es2, mnv2, mvn2) = {-# SCC "d" #-} dependencyEdges acc ndeps in > -- Now we can claim v2 as the label for this node n. > -- Look up vdep for each dependency ndep and add an edge from the vdep to v2. > let {(v4, es4, mnv4, mvn4) = {-# SCC "e" #-} List.foldl' ( > \(v3, es3, mnv3, mvn3) ndep -> > case {-# SCC "f" #-} Map.lookup ndep mnv3 of > Just vdep -> (v3, (vdep, v2):es3, mnv3, mvn3) > Nothing -> error $ "this node should have been added already: " ++ show ndep > ) (v2, es2, mnv2, mvn2) ndeps } in > assert (v2 == v4) > assert (mvn2 == mvn4) > assert (mnv2 == mnv4) > -- Finally, add this node to the accumulator and then recurse. > dependencyEdges (v2+1, es4, {-# SCC "g" #-} Map.insert n v2 mnv2, {-# SCC "h" #-} Map.insert v2 n mvn2) ns with the following profile: > dependencyGraph Dataflow 4395 1 0.0 0.0 93.4 99.9 > getRootDFNodes Dataflow 4397 5 0.0 0.0 0.0 0.0 > dependencyEdges Dataflow 4396 282 0.0 0.0 93.4 99.9 > a Dataflow 4407 104 0.0 0.0 0.0 0.0 > j Dataflow 4399 178 87.6 99.9 93.4 99.9 > b Dataflow 4417 75 0.0 0.0 0.0 0.0 > g Dataflow 4405 103 0.1 0.0 0.2 0.0 > con2tag_DFBool# Representation 4419 1972 0.0 0.0 0.0 0.0 > con2tag_DFReal# Representation 4414 186890 0.1 0.0 0.1 0.0 > con2tag_DFNode# Representation 4413 1204 0.0 0.0 0.0 0.0 > h Dataflow 4404 103 0.0 0.0 0.0 0.0 > e Dataflow 4403 103 0.0 0.0 4.8 0.0 > f Dataflow 4412 174 2.9 0.0 4.8 0.0 > con2tag_DFBool# Representation 4420 245794 0.0 0.0 0.0 0.0 > con2tag_DFReal# Representation 4416 25772482 1.9 0.0 1.9 0.0 > con2tag_DFNode# Representation 4415 2068 0.0 0.0 0.0 0.0 > d Dataflow 4402 103 0.0 0.0 0.0 0.0 > c Dataflow 4401 103 0.0 0.0 0.0 0.0 > nodeDependencies Dataflow 4406 103 0.0 0.0 0.0 0.0 > i Dataflow 4400 178 0.6 0.0 0.7 0.0 > con2tag_DFBool# Representation 4418 48230 0.0 0.0 0.0 0.0 > con2tag_DFReal# Representation 4410 5045646 0.1 0.0 0.1 0.0 > con2tag_DFNode# Representation 4409 1928 0.0 0.0 0.0 0.0 Is this a space leak, or is my algorithm just silly? (It could well be the latter...) I've tried adding random bangs, to no effect. So, can anyone help me? :) Cheers Ben

4 4

research topics
by Henrique Ferreiro 01 Jan '08

01 Jan '08

Hi haskellers! I am a postgraduate student interested in functional programming and Haskell. I would appreciate if someone could elaborate on which are the current hot topics of research in this area, and related to Haskell, of course. In particular, I am interested in compiler implementation. Thanks in advance. -- Henrique Ferreiro <henrique.ferreiro(a)gmail.com>

1 0

Re: [Haskell-cafe] How to convert number types.
by L.Guo 01 Jan '08

01 Jan '08

Ah, thanks, it is my fault, for mis-understanding the hint from GHC. And what is the difference between fromIntegral and fromInteger ? ------------------ L.Guo 2008-01-01 ------------------------------------------------------------- From: Mark T.B. Carroll At: 2008-01-01 01:42:37 Subject: Re: [Haskell-cafe] How to convert number types. Perhaps fromIntegral does what you want? Mark

2 1

How to convert number types.
by L.Guo 01 Jan '08

01 Jan '08

Hi MailList Haskell-Cafe: I am a new haskeller. And was farmilar with C. When tring to do some calculate, like this: input = 5 :: Int factor = 1.20 :: Float output = factor ** (toFloat input) I found that I do not know any function could do just what 'toFloat' should do. What should I do then ? Regards -------------- L.Guo 2008-01-01

4 3

A "commutative diagram" conjecture about applicative functors
by Robin Green 31 Dec '07

31 Dec '07

I am proving various statements relating to applicative functors, using the Coq proof assistant (I am considering only Coq terms, which always terminate so you don't have to worry about _|_). However, I'm not sure how to go about proving a certain conjecture, which, translated back into Haskell and made more specific to make it easier to think about, looks like this (assuming Control.Applicative and Control.Arrow are imported): "For all applicative functors: \f x -> fmap second f <*> fmap ((,) (0::Int)) x is equivalent to \f x -> fmap ((,) (0::Int)) (f <*> x)" McBride and Patterson give four laws for applicative functors in their paper "Functional Pearl: Applicative programming with effects". Can these laws be used to prove this conjecture for all applicative functors satisfying those laws? -- Robin P.S. I realise this might not look like a "commutative diagram conjecture", but as I said, I've made it more specific - my actual conjecture is more general, but hopefully if I can understand how to prove the specific one, I'll be able to prove my real one in short order.

3 4

Getting links to Haddock documentation in Hackage
by Adam Langley 31 Dec '07

31 Dec '07

Some packages[1] have links on their Hackage pages to the haddock generated documentation for each exported module[2]. However, many[3] don't. What's the secret to getting this generated documentation to work with Hackage? Even packages for which `runhaskell Setup.lhs haddock` runs don't (always) get the magic links. Cheers, AGL [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bzlib-0.4.0.1 [2] http://hackage.haskell.org/packages/archive/bzlib/0.4.0.1/doc/html/Codec-Co… [3] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar-0.1.1.1 -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org 650-283-9641

2 1

The semantics of constructor patterns
by Cristian Baboi 31 Dec '07

31 Dec '07

In section 4.3.3., chapter 4: Structured types and the semantics of pattern-matching, by S.Peyton Jones and Philip Wadler, there is this equation: Eval[[\(s p1 p2 ... pt).E]] (s a1 a2 ...at) = Eval[[\p1 ... \pt.E]] a1 ... at The text say: "To apply \(s p1 ... pt).E to an argument A we first evaluate A to find out what sort of object it is." "Finally, if A was built with the same constructor as the patern, then the first rule applies." What I don't get it : (s a1 a2 ... at) must be the value of A in the semantic domain. Let call that value a. Then how can one know if a was built with (s a1 a2 ... at) and not with (egg b1 b2) ?

3 4

easy cabal tasks
by Duncan Coutts 30 Dec '07

30 Dec '07

People are often unsure about where they can help out with Cabal. One thing we can do to make that easier is to point out smaller simpler tasks that people might like to have a go at. We have a list of tasks that are marked as easy or very easy: http://hackage.haskell.org/trac/hackage/report/13 This list is also linked from the hackage trac web page ("Easy tickets") http://hackage.haskell.org/trac/hackage/ For people reporting bugs and working with the hackage/cabal trac, look out for tasks that you think could be done by a new or relatively new contributor and mark the bug's difficulty appropriately. Please also give plenty of detail on what the solution should involve and pointers to other documentation as appropriate. Duncan

1 0

Type-system fun: a type-safe embedding of System F Lambda Calculus into Haskell
by Ryan Ingram 30 Dec '07

30 Dec '07

(The full code used for this message is available at http://ryani.freeshell.org/haskell/systemf.hs) System F is the polymorphically typed lambda calculus. It is strongly typed but allows polymorphic functions like "id". id is represented as follows: > eId = EGamma "A" (ELam "x" TVar EVar) which represents > \A -> \x:A -> x that is, a function that takes a type and a single argument of that type and returns its argument. This embedding only allows well-typed terms to be constructed; the Haskell typechecker verifies that a term is well-typed. I include a full compiler which converts terms into Haskell functions (albeit not-very-efficient ones). A sample session with GHCi follows: GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Ok, modules loaded: SystemF. Prelude SystemF> eId \A a:A -> a Prelude SystemF> :t eId eId :: NExpr (a :-> (a -> a)) Prelude SystemF> :t eBottom eBottom :: NExpr (a :-> a) Prelude SystemF> eBottom \A -> fix (\a:A -> a) Prelude SystemF> putStrLn $ showExprExplicit eBottom (EGamma "A" (EFix (ELam "a" TVar EVar))) Prelude SystemF> tInt I# Prelude SystemF> :t (TPrim "I#" (undefined :: Integer)) (TPrim "I#" (undefined :: Integer)) :: TypRep Integer ts Prelude SystemF> :t tInt tInt :: TypRep Integer ts Prelude SystemF> eK \A B a:A b:B -> a Prelude SystemF> eFact fix (\rec:(I#->I#) z:I# -> (\A -> if#) I# (eq# z 0) 1 (times# z (rec (minus# z 1)))) Prelude SystemF> :t eFact eFact :: NExpr (Integer -> Integer) Prelude SystemF> compile eFact 5 120 Prelude SystemF> putStrLn $ showExprExplicit eFat <interactive>:1:28: Not in scope: `eFat' Prelude SystemF> putStrLn $ showExprExplicit eFact (EFix (ELam "rec" (TArrow (TPrim I#) (TPrim I#)) (ELam "z" (TPrim I#) (EAp (EAp (EAp (ETypAp (EGamma "A" (EPrim if#)) (TPrim I#)) (EAp (EAp (EPrim eq#) EVar) (EPrim 0))) (EPrim 1)) (EAp (EAp (EPrim times#) EVar) (EAp (EPush EVar) (EAp (EAp (EPrim minus#) EVar) (EPrim 1)))))))) Prelude SystemF> :t (whnf (EAp eFact (EPrim "6" 6))) (whnf (EAp eFact (EPrim "6" 6))) :: Expr Integer NDecl NDecl Prelude SystemF> (whnf (EAp eFact (EPrim "6" 6))) if#*** Prelude SystemF> extractPrim (whnf (EAp eFact (EPrim "6" 6))) Just 720

1 0