- Haskell-Cafe - Haskell.org

relational data representation in memory using haskell?
by Marc Weber 22 May '08

22 May '08

I'm kind of stuck that's why I'm posting here to ask wether this makes sense at all, maybe someone else has already done it? What I'd like to have: Some way representing relational data which is typically stored in databases such as Postgresql.. Rewriting something like Postgresql in haskell would take ages.. So I'd be satisfied with having in memory representation only (this would fit the HAppS state system very well .. :) Why ? * type safety * less conversions compared to SQL data * no need to switch processes, parse SQL etc so maybe it's even faster? (a small benchmark showed that inserting 20000 Ints into a list was 8 times faster than using MySQL parsing 20000 INSERT INTO x (1) statements ) I'd like to illustrate two different ideas using a small example: (A) data CD = CD { title :: String, tracks :: [ Track ] } data Track = Track { track :: String, cd :: CD } data PDB = PDB { cds :: Set CD, tracks :: Set Track } because it's not using foreign ids but kind of pointers I'll call this the pointer method using uniq ids it would look like this: (B) data CD = CD { id : Int, title :: String, tracks :: [Int ] } data Track = Track { trackId :: Int, track :: String, cd :: Int } data IDB = IDB { cds :: Map Int CD, tracks :: Map Int Track } I will call it I DB (I = using ids) PDB: pro : * less work when doing joins (no need to look foreign rows up) con : * you need uniq ids or such when serializing to disk * When updating a track you'll also have to update the pointer stored in cds. and if you had another table shelfs.. this had to be updated as well.. IDB: the other way round I find the idea not using any lookups when using joins appealing. Of course having a simple data Table = Table Map UniqId Rec isn't enough, sometimes you need more than one index or even a multi index: data Table = Table { byId :: Map Int Rec , byNameAndAge :: Map String (Map Int (Set Rec)) } Note that I've used Set here as well because this index does'nt have to be uniq! starting to write an insertTable :: Table -> Rec -> Table more than twice is getting tedious.. Of course you can start using some type hackery to insert a rec into all maps automatically.. but you'll get into trouble making the type system apply the best index not the first matching one. (I bet this could be done using HList etc somehow as well.. ) So my current attempt is defining the database using some data types and make template haskell derive those insertIntoTable and update functions. I've added the draft below. But before continuing spending much time on it I'd like to get your advice: Is there a chance that it will pay off? Some general considerations: haskell solution con: haskell can get close to C but in general it may be >10 times slower when not caring too much about design or writing low level (see recent thread about md5 or one where David Roundy has said something about a matrix thread: only 10 times slower?) Using a garbage collector on database data (some hundred MB) might not be the optimal way because I feel you can tell exactly when you no longer need a piece of allocated memory here? So some time might be wasted. projects tend to run longer as expected.. And if data no longer fits into memory .. :(... -> bad performance I think systems such as postgresql do scale much better if you have some gbs of data and only use the most recent X records frequently.. So maybe you'll have to spend time later which you've won by using a haskell relational data representation in memory only.. Another solution: use clusters - I don't have any experience. pro: much more safety (STM, type system ..) there are less possibilities making compared to C / PHP etc Do you also think (A) is more interesting because some load (looking up foreign keys) is moved on insert / delete and update operations taking less time in but are called more frequently thus maybe reducing peak load on queries? Of course some time would have to be spend on queries wich might look like this: let queryresult = $(query ( tables + constraints + relations ) ) db automatically generating the query function taking into account expected index cardinality etc.. Any comments, suggestions, links to existing solutions (except coddfish, haskelldb) ? Marc Weber draft ============= types represeting tables and db ======================== module RDMH.Types where import Language.Haskell.TH import Language.Haskell.TH.Syntax data Uniqueness = Uniq | NotUniq deriving (Show, Eq) data ModifyMode = InsertOnly | UpdateInsert | UpdateInsertDelete deriving (Show, Eq) type TypeS = String -- a name of a data type (data A = ..) data Index = I { uniqueness :: Uniqueness , key :: Exp -- a fuction rec -> key , subkeys :: [ Index ] , keyType :: TypeS -- the key type (this *should* be determined by the function.. But I don't know yet how to do it.. Probably using some GHC API magic -- , expectedCardinality :: Int -- how should this look like exactly? This will be used to select the best indexes } deriving (Show, Eq) -- Int is negative weight / cardinality. -- If you issue a query having two contstraints on types beeing indexed the one having biggest cardinality is taken first -- first type:` -- convinient function to get the type of a name - see TestCase.hs t = ConT . mkName -- type (either key or row) k = VarE . mkName -- gets the key -- app (VarE $ mkName "fst" ) -- a table representation data Table = Table { tableName :: String , row :: TypeS -- this row type must be an instance of Eq , indexes :: [ Index ] -- [ ( [ mkName "Int", mkName "String" ]] is represented as Map Int ( Map String rec ) -- , history :: Bool -- to be implemented. Each time a record is updated the original row should be saved somehow somewhere , modify :: ModifyMode -- , insertTimeStamp :: Bool -- , updateTimeStamp :: Bool } deriving (Eq, Show) data DB = DB { dbName :: String , tables :: [ Table ] , oneToN :: [ (Table, Table, String) ] -- String must be set if you want two relations to the same table (eg one ticket has foreign inbound and outbound flight) -- , nToM :: [ ( Table, Table ) ] } ============= example use case ======================================= {-# OPTIONS_GHC -XTemplateHaskell #-} module TestCase where import Language.Haskell.TH import RDMH.Types import RDMH.TH import Data.Time -- the data data RCD = CD { title :: String , artist :: String , year :: Int } data RTrack = Track { trackTitle :: String , recordingDate :: UTCTime } -- a track table with two indexes title and recordingDate trackT = Table "track" (t "RTrack") -- row type -- indexes: [ I NotUniq (k "trackTitle" ) [] (t "String") , I NotUniq (k "recordingDate" ) [] (t "UTCTime") ] UpdateInsertDelete -- a cd table with two indexes title and year cdT = Table "cd" (t "RCD" ) -- row type -- indexes: [ I Uniq (k "title" ) [] (t "String") , I NotUniq (k "year" ) [] (t "Int") ] UpdateInsertDelete -- the db: both tables and a simple relation db = DB "cdDB" [ cdT, trackT ] [ OneToN cdT trackT "" ) ] $(createDB db)

6 16

A chance to share your experience
by Simon Peyton-Jones 22 May '08

22 May '08

Friends I know for a fact that many of you are using Haskell successfully for real applications. Yet none of you have sent me an offer of a presentation at the Commercial Users of Functional Programming workshop, which happens in late Sept. I'm the program co-chair, and I confidently expecting several Haskell offers... but not one so far. I am sad. I am very sad. Make me happy! I'm sure you are very busy making your business work. But think what fun it'd be to share your experience with others, meet other people with similar experiences, recruit bright students to your company... Happily, there is still time. The deadline for offers is 2nd June. All we need by then is a short summary of what you think you might say. You don't have to write a paper (not now, not ever). Your presentation does not have to be highly technical. On the contrary, the emphasis is on the process issues that surround functional programming: convincing management, changes to software development, testing, benefits, costs, successes, concerns. I'm going to the Lake District for a week's holiday next week (it's half term in the UK). Please send me a lovely full mailbox to come back to. The CFP is below, and at http://cufp.galois.com/. best wishes Simon Commercial Users of Functional Programming Workshop (CUFP) 2008 26 September 2008, Victoria, British Columbia ============== CALL FOR PRESENTATIONS ====================== Presentation proposals due 2 June 2008 http://cufp.functionalprogramming.com Functional Programming As a Means, Not an End Sponsored by SIGPLAN Co-located with ICFP 2008 _________________________________________________________________ Functional languages have been under academic development for over 25 years, and remain fertile ground for programming language research. Recently, however, developers in industrial, governmental, and open source projects have begun to use functional programming successfully in practical applications. In these settings, functional programming has often provided dramatic leverage, including whole new ways of thinking about the original problem. The goal of the CUFP workshop is to act as a voice for these users of functional programming. The workshop supports the increasing viability of functional programming in the commercial, governmental, and open-source space by providing a forum for professionals to share their experiences and ideas, whether those ideas are related to business, management, or engineering. The workshop is also designed to enable the formation and reinforcement of relationships that further the commercial use of functional programming. Speaking at CUFP If you use functional programming as a means, rather than as an end, we invite you to offer to give a talk at the workshop. Alternatively, if you know someone who would give a good talk, please nominate them! Talks are typically 30-45 minutes long, but can be shorter. They aim to inform participants about how functional programming played out in real-world applications, focusing especially on the re-usable lessons learned, or insights gained. Your talk does not need to be highly technical; for this audience, reflections on the commercial, management, or software engineering aspects are, if anything, more important. You do not need to submit a paper! If you are interested in offering a talk, or nominating someone to do so, send an e-mail to jim (dot) d (dot) grundy (at) intel (dot) com or simonpj (at) microsoft (dot) com by 2 June 2008 with a short description of what you'd like to talk about or what you think your nominee should give a talk about. Such descriptions should be about one page long. Program Plans CUFP 2008 will last a full day and feature an invited presentation from Michael Hopcroft, the product unit manager for the forthcoming release of Microsoft Visual Studio F#. Additionally, the program will include a mix of presentations and discussion sessions. Topics will range over a wide area, including: * Case studies of successful and unsuccessful uses of functional programming; * Business opportunities and risks from using functional languages; * Enablers for functional language use in a commercial setting; * Barriers to the adoption of functional languages, and * Mitigation strategies for overcoming limitations of functional programming. There will be no published proceedings, as the meeting is intended to be more a discussion forum than a technical interchange. Program Committee * Lennart Augustsson <lennart (dot) augustsson (at) gmail (dot) com> * Matthias Blume <blume (at) tti-c (dot) org> * Adam Granicz <granicz (dot) adam (at) intellifactory (dot) com> * Jim Grundy (co-chair) <jim (dot) d (dot) grundy (at) intel (dot) com> * John Lalonde <lalonde (at) abstrax (dot) com> * Andy Martin <akmartin (at) us (dot) ibm (dot) com> * Yaron Minsky <yminsky (at) janestcapital (dot) com> * Simon Peyton Jones (co-chair) <simonpj (at) microsoft (dot) com> * Ulf Wiger <ulf (dot) wiger (at) ericsson (dot) com> This will be the fifth CUFP, for more information - including reports from attendees of previous events - see the workshop web site: http://cufp.functionalprogramming.com

1 0

Re: [Haskell-cafe] one-way monads
by Dan Doel 21 May '08

21 May '08

On Tuesday 20 May 2008, ajb(a)spamcop.net wrote: > Actually, it's true less than 50% of the time. In particular, it's > not true of any monad transformer. Sure it is. Any particular transformer t typically comes with some particular way of writing a function of type t m a -> m a (you may have to throw away some t-related stuff, of course). Since a specific transformed monad is built from a specific monad, and a specific transformer, and specific transformers are likely to have a function of type t m a -> m a, and specific monads are likely to have functions of type m a -> a, you can compose them to get a function of type t m a -> a for the specific monad t m. And so on for transformed-transformed monads. :) That only fails if either of the specific pieces fails to have the right function, which happens well under 50% of the time, I think (IO and STM are the ones that immediately occur to me (barring a certain evil function), although you could make a case for ST by technicality; no failing transformers come to mind (except CCT if we're counting ST), but I haven't wracked my brain very hard). -- Dan

7 6

Return user state in Parsec
by Maciej Podgurski 21 May '08

21 May '08

Hi, I'm currently writing a parser using the Parsec library. What I want is to store the order of each subparser called in a user state. So every single parser will be marked with a label that is stored in a special treelike structure when the parser is run. My problem is to return the last state of this structure when a parse error occurred. This information shall be used to display a kind of stack trace showing the order of the parser calls for debug purposes. Any ideas how to achieve this? Thanks, Maciej

2 1

Installing Cabal-Install
by Aditya Siram 21 May '08

21 May '08

Hi all, I am trying to install cabal-install so I can install xmonad-contrib. I have all the dependancies in place but when I do: runhaskell Setup.lhs build I get: Hackage/Types.hs:19:29: Module `Distribution.Version' does not export `Dependency' Any ideas? Thanks ... Deech _________________________________________________________________ Make every e-mail and IM count. Join the i’m Initiative from Microsoft. http://im.live.com/Messenger/IM/Join/Default.aspx?source=EML_WL_ MakeCount

2 2

ghc-pkg package.conf files?
by Galchin, Vasili 21 May '08

21 May '08

Hello, I fairly innocuous question ;^). How does ghc-pkg know where are the *package.conf files are located? Regards, Vasili

2 3

RealFloat constraint on Complex type
by Conal Elliott 21 May '08

21 May '08

GHC's (maybe Haskell98's?) Complex type is defined with a RealFloat constraint on type type itself, rather than on some of the instances and functions: data (RealFloat a) => Complex a = !a :+ !a I think the practice of constraint in type definitions is generally discouraged, and I'm wondering if there are reasons other than history for having the constraint here. Is removing it on the table for Haskell'? I just got bit by what I think is a typical problem. I added a VectorSpace instance for 'Complex a' and discovered that my 'a' must be in RealFloat, even though I use only zero, addition, subtraction, and scaling. I suspect this gripe has been raised before ... Thanks, - Conal

5 4

one-way monads
by Zsolt SZALAI 21 May '08

21 May '08

Hi! Now, i'm getting familiar with monads, but there is a little discredit about one-way monads. For example, in monads presented in Monads for Functional Programming by Philip Wadler, they are all two-way monads, internal data can be extracted from the monad, and these data, call them state, are in deed _local_ to a function using the monadic computation, so the state there is just a little magic, and they are really just functions(as in a pure language). An other example is Random. I've figured out, that when initializing a generator, it uses the actual timestamp and cputime to initialize. If it wouldnt happen, two distinct uses of Random in a program would result the same random number sequence. Here comes IO and one-way monads, where the internal state can not be extacted, and seems, that the internal data is global to the program. Hows that could be? Is it just because main::IO() or because the implementation of IO uses external C functions and there are no internal state in the monad itself at all? And why one can not write a function that makes an IO computation and the return type does not include and IO contructor? It is a feature of the language and specific to IO, or anybody could write a monad with this property(one-way), assuming the implementation does not use external languages? Or the one-way property is just that, there is no such functions, that allow extracting internal data? Also, is there any other monad, that has the one-way property? Thanks, -- Zsolt

7 6

are there any good c parsers + ast builders available for haskell?
by Carter Tazio Schonwald 21 May '08

21 May '08

Hello, I'm thinking about having a go at writing some simple static analysis tools for C, and I think using Haskell would make it a happier time coding wise, the question being, are there preexisting parsing tools for C available for haskell? many thanks -Carter

2 2

Performance: MD5
by Andrew Coppin 20 May '08

20 May '08

Hi folks. OK, try this: darcs get http://darcs.orphi.me.uk/MyMD5 cd MyMD5 ghc -O2 --make md5sum md5sum <some large filename> On my PC, it takes 3.5 seconds to compute the MD5 hash of a 10 MB file. For comparison, the md5.exe I downloaded from the Internet does it instantaneously. It's literally so fast I can't even time it. As far as I know, my program always produces the *correct* answer, it just takes far too long to do it. If anybody has any interesting insights as to why my version is so damned slow, I'd like to hear them. (Indeed, a description of the process for tracking the problem down would also be useful!) [Much to my bemusement, when I had a look at the code, I discovered that tucked away in a corner somewhere, it reads a ByteString from disk and instantly converts it to [Word8]. Uh... oops? Anyway, eliminating this changed the numbers I get from the profiler, but it's still far too slow.]

14 47