March 2007 - Haskell-Cafe

Duplicate instance declaration
by Bas van Dijk 23 Mar '07

23 Mar '07

Hello, I'm making an assembly language DSEL in Haskell (just for fun) very similar to the one from Russel O' Conner in [1] I'm trying to specify a 'mov' instruction. A 'mov' instruction has two operands: a destination and a source. There are various constraints on the operands. They have to be of the same size (8-, 16- or 32-bit) and they have to be in a specific format: mov reg reg mov reg mem mov mem reg mov reg imm mov mem imm where reg, mem and imm are register, memmory and immediate values respectively. I would like the type system to check as many constraints as possible. I've managed to get the size constraints working. See the source below this mail. For example the following are all type-correct: valid1 = mov EAX EBX valid2 = mov BX DX valid3 = mov AH AL And the following doesn't pass the type checker: invalid1 = mov EAX BX -- Couldn't match expected type `Bit16' against inferred type `Bit32' I would also like to get the formatting constraints working. However the solution in the code below gives a "Duplicate instance declarations" error. If I -fallow-overlapping-instances than the type checker goes into an infinite loop. I would like to know why this is happening and if there's a way to fix it. Thanks in advance, Bas van Dijk [1] The Monad.Reader Issue 6, Russel O' Conner, Assembly: Circular Programming with Recursive do, http://haskell.org/sitewiki/images/1/14/TMR-Issue6.pdf \begin{code} {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-} module ASM where import Data.Word -- TODO: Not finished yet... -- This is the type of instructions. -- It's going to be a Monad like the one from Russel O'Conner: data AsmM = AsmM deriving Show -- Sizes of registers, memmory or immediate values data Bit32 data Bit16 data Bit8 -- A type-level function that determines the size of a value class Size x size | x -> size -- Types of values class Reg reg class Mem mem class Imm imm -- General Purpose Registers -- Accumulator data EAX = EAX; instance Reg EAX; instance Size EAX Bit32 data AX = AX; instance Reg AX; instance Size AX Bit16 data AH = AH; instance Reg AH; instance Size AH Bit8 data AL = AL; instance Reg AL; instance Size AL Bit8 -- Base data EBX = EBX; instance Reg EBX; instance Size EBX Bit32 data BX = BX; instance Reg BX; instance Size BX Bit16 data BH = BH; instance Reg BH; instance Size BH Bit8 data BL = BL; instance Reg BL; instance Size BL Bit8 -- Counter data ECX = ECX; instance Reg ECX; instance Size ECX Bit32 data CX = CX; instance Reg CX; instance Size CX Bit16 data CH = CH; instance Reg CH; instance Size CH Bit8 data CL = CL; instance Reg CL; instance Size CL Bit8 -- Data data EDX = EDX; instance Reg EDX; instance Size EDX Bit32 data DX = DX; instance Reg DX; instance Size DX Bit16 data DH = DH; instance Reg DH; instance Size DH Bit8 data DL = DL; instance Reg DL; instance Size DL Bit8 -- Memmory data Mem32 = Mem32 Word32; instance Mem Mem32; instance Size Mem32 Bit32 data Mem16 = Mem16 Word32; instance Mem Mem16; instance Size Mem16 Bit16 -- Instructions class Mov dest src where mov :: dest -> src -> AsmM instance ( Size dest size , Size src size , MovFormat dest src ) => Mov dest src where mov d s = AsmM -- TODO: Not finished yet... class MovFormat dest src -- If I have more than one MovFormat instance than I get a -- "Duplicate instance declaration" error: instance (Reg dest, Reg src) => MovFormat dest src instance (Reg dest, Mem src) => MovFormat dest src instance (Mem dest, Reg src) => MovFormat dest src instance (Mem dest, Imm src) => MovFormat dest src instance (Reg dest, Imm src) => MovFormat dest src -- Tests valid1 = mov EAX EBX valid2 = mov BX DX valid3 = mov AH AL -- invalid1 = mov EAX BX -- Couldn't match expected type `Bit16' against inferred type `Bit32' -- invalid2 = mov EAX (Mem32 0) -- No instance for (Reg Mem32) \end{code}

2 2

problem in installing hat
by Vikrant 23 Mar '07

23 Mar '07

<hat(a)haskell.org>Hi, I wanted to try out hat debugger. I tried to install it according to instructions. I downloaded the source tgz and did following sequence of operations tar -xvzf hat-2.05.tar.gz cd hat-2.05 ./configure make it gives me following error! MkProg: hmake: the compiler 'ghc' is not known. Stop - hmake dependency error. I have following system configuration. ghc - Glasgow Haskell Compiler, Version 6.4.1, for Haskell 98, compiled by GHC version 6.4.1 hugs - Version: 20050308 hmake - version 3.10 (2005-03-11) gcc - gcc (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5) can anybody help me in this? Regards, Vikrant

1 0

Re: [Haskell-cafe] XML Validation and Digestion in Haskell
by Chris Eidhof 23 Mar '07

23 Mar '07

Hey Aron, I think you intended to CC Haskell Café as well. HaXml has support for DtdToHaskell, but HXT supports validating with a Relax NG validator. I guess the best way to figure it out is thoroughly read the documentation. -chris On Mar 22, 2007, at 10:40 PM, Arun Suresh wrote: > thanks for the feedback you guyz.. > > First off.. I went through the HaXml documentation.. It looks > pretty promising.. > and as far as HXT is concerned.. I guess ill be spending the > weekend grappling with the concept of Arrows and monads in general :) > > I dont know if HXT or HaXml offers it.. but I was wondering if > either of them provides some sort of schema compilation facility.. > (a la XmlBeans.. for those from the Java world).. basically I was > wondering if given an XML schema, is there a utility that will > generate a Haskell type hierarchy from the same ?? > > regards > Arun > > > On 3/23/07, Chris Eidhof < chris(a)eidhof.nl> wrote:Don't spend too > much time on the various libraries though. I tried > some simple things with Haskell and XML, but I found it really hard > to actually parse a simple document. You really don't want to write > your own parser. > > The only tool that worked for me was HXT, which is based on arrows. > These are pretty hard to grasp right away, but really powerful. I > really like the way they are used in HXT, but it still feels a bit > weird sometimes. > > Good luck, and keep us posted. > > -chris > > On Mar 22, 2007, at 7:52 AM, Andrew Wagner wrote: > > > Hi Arun, > > Your problem description seems a little vague - which is > > understandable, considering how embedded in your business model > it is. > > As for general recommendations, I'm no guru, but I would suggest > > looking at the existing XML libraries in Haskell [1], and if that's > > not powerful enough, check out parsec[2] for building a custom > parser. > > I think to get more specific recommendations, you would need to give > > more details about the problem. Hope this helps somewhat. Andrew > > > > [1]: http://www.haskell.org/haskellwiki/Libraries_and_tools/ > > Web_programming#XML_2 > > [2]: http://www.cs.uu.nl/people/daan/download/parsec/parsec.html > > > > > > On 3/22/07, Arun Suresh < arun.suresh(a)gmail.com> wrote: > >> Hi.. > >> > >> I am currently working on a project where basically we do a lot of > >> XML > >> validation and digestion. For example : > >> We recieve an XML document A, if the document passes schema > >> validation, we > >> do some business level validations, then from A, we create XML > >> digests B, C > >> and D. > >> Our code-base is written completely in Java. We had earlier tried > >> using > >> XSLT, but it became too unwieldy to manage (we ended up making > >> calls to > >> other Java classes from the XSLT engine) > >> > >> The problem we are facing right now is that we have huge > >> hierarchies of > >> Validators, Digestors and Contexts. It just doesnt look right. I > >> just cant > >> help but wonder if theres a better way of doing this... > >> > >> I have been trying to get my hands dirty with Haskell for a couplo > >> weeks > >> now. all the while keeping the problem at hand in the back of my > >> mind.. I > >> just dont seem to be see how applying functional programming > >> concepts can > >> help in this scenario.. Was wondering if somebody could probably > >> give me > >> some pointers.. > >> > >> Regards > >> Arun > >> > >> > >> > >> > >> > >> > >> _______________________________________________ > >> Haskell-Cafe mailing list > >> Haskell-Cafe(a)haskell.org > >> http://www.haskell.org/mailman/listinfo/haskell-cafe > >> > >> > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

XML Validation and Digestion in Haskell
by Arun Suresh 23 Mar '07

23 Mar '07

Hi.. I am currently working on a project where basically we do a lot of XML validation and digestion. For example : We recieve an XML document A, if the document passes schema validation, we do some business level validations, then from A, we create XML digests B, C and D. Our code-base is written completely in Java. We had earlier tried using XSLT, but it became too unwieldy to manage (we ended up making calls to other Java classes from the XSLT engine) The problem we are facing right now is that we have huge hierarchies of Validators, Digestors and Contexts. It just doesnt look right. I just cant help but wonder if theres a better way of doing this... I have been trying to get my hands dirty with Haskell for a couplo weeks now. all the while keeping the problem at hand in the back of my mind.. I just dont seem to be see how applying functional programming concepts can help in this scenario.. Was wondering if somebody could probably give me some pointers.. Regards Arun

4 3

random number generators
by david karapetyan 22 Mar '07

22 Mar '07

hi, i have been trying to learn haskell and i would like to translate the following object-oriented pseudo-code into working haskell code but i'm stumped on how to write the next function in the haskell code. any help is appreciated. class Random ... end ran = Random.new(300) ran.next() <- this call generates a random number ran.next() <- this one generates a different random number so far what i have in haskell is: data Random = Ran Int Int next :: Random->Int <- i have no idea how to write the next function that would give me the desired effect because the object in the object-oriented code can remember how many times 'next' was called and i would like to do the same for 'ran' in the haskell code. ran = Ran 300 0 next ran <- this generates a random number next ran <- this generates another random number but since haskell is purely functional it is going to be the same as from the previous call of 'next' which is not what i want

2 1

Re: [Haskell-cafe] Newbie: Is 'type' synonym hiding two much?
by Dmitri O.Kondratiev 22 Mar '07

22 Mar '07

> Now, in the 17.5 section of a book one may see the following declarations: > > succeed :: b -> Parse a b > > *Before looking at 'succeed' function definition* one may think that > 'succeed' is a function of *one* argument of type 'b' that returns object of > type 'Parse a b'. <Antti-Juhani Kaijanaho wrote> That's what it is. However, without looking at the definition of Parse a b, you can't tell whether that is a function or not, and therefore all you can say about succeed is that it takes *at least* one argument. </Antti-Juhani Kaijanaho wrote> At least something to know :) I'll try to remeber this idiom. > Then I do this substitution *myself as a Haskell runtime* and get in > the result the following declaration of a * real > function that Haskell runtime* works with: <Antti-Juhani Kaijanaho wrote> I'm not sure why you feel the need to talk about runtime. This all happens at compile time. </Antti-Juhani Kaijanaho wrote> I wrote "runtime" because I didn't know how in own word to term inteprepter (GHCi) and compiler (GHC). Both of them will deal with this task/ > 2. Should I search through main and imported modules for treacherous 'type' > constructs? <Antti-Juhani Kaijanaho wrote> They are not treacherous. But yes, if you want to know what a type stands for, you need to look it up. The "treacherous" thing here is that in Haskell, returning a function is the same as taking one more parameter. This may feel strange at first, but it is a very important idiom and you do need to learn to live with it if you want to use Haskell. </Antti-Juhani Kaijanaho wrote> I see now, got it! Thanks. > > succeed :: b -> Parse a b > > *Before looking at 'succeed' function definition* one may think that > 'succeed' is a function of *one* argument of type 'b' that returns object of > type 'Parse a b'. > > Yet, function definition given in the book is: > > succeed val inp = [(val, inp)] <Ian Lynagh wrote> It's common to instead write this as succeed :: b -> Parse a b succeed val = \inp -> [(val, inp)] so the definition fits the type signature better. </Ian Lynagh wrote> Yes, that make more sense to me - function that returns a "customized" function <Ian Lynagh wrote> The main advantage of the synonym is when you are /using/ the Parser library, so you can put Parser String's in sequence etc without needing to know that internally they're implemented as a function. </Ian Lynagh wrote> Do you mean that if insted of type sysnonym I would use ADT built with 'data': data Parser a b = Parser (a -> [(b, [a])]) succeed :: b -> Parse a b succeed val = Parser (\inp -> ...) then I would not be able to put "put Parser String's in sequence etc without needing to know that internally they're implemented as a function" ? Anyway, I will try to implement this version of Parser as well. <Bernie Pope wrote> I think the main issue here is that from the "user's perspective" the Parse type should be (or is) abstract. Users of Parse should not really have to know how it is internally implemented. But implementors of Parse will (of course) be concerned with those details. How you look at the Parse type depends on which camp you belong to: implementor or user. </Bernie Pope wrote> Very good observation Bernie, thanks. Yet I need to play more with Parser type to justify it for this case :) Thanks guys for all your feedback! It really helps!

1 0

Newbie: Is‘type’ synonym hiding two much?
by Dmitri O.Kondratiev 22 Mar '07

22 Mar '07

I am learning Haskell working through Simon Thompson book "Haskell The Craft of Functional Programming" (second edition). Solving problems in the book with more or less success I arrived almost to the end of the book at the section 17.5 "Case study: parsing expressions". Most probably the question I am going to ask here is very stupid, so please bear with me. In any case, after going so far in the book I felt certain that I know what function declaration means. So I thought that declaration: F :: a -> b -> c Is the same as: F :: a -> (b -> c) And means either: - a function 'f' of one argument of type 'a' that returns a function of type (b -> c), or it can also be interpreted as: - a function 'f' of two arguments of type 'a' and 'b' returning value of type 'c' Now, in the 17.5 section of a book one may see the following declarations: succeed :: b -> Parse a b *Before looking at 'succeed' function definition* one may think that 'succeed' is a function of *one* argument of type 'b' that returns object of type 'Parse a b'. Yet, function definition given in the book is: succeed val inp = [(val, inp)] Looking at this definition, I am inclined to think that 'succeed' is a function of *two* arguments named 'val' and 'inp' in the definition ! How can such a definition be correct? Ok, lets see what is this 'Parse a b' type is: type Parse a b = [a] -> [(b, [a])] So how does this help to make definition 'succeed val inp = [(val, inp)]' sound right? Well, the only way for me to make sense out of this is as follows. In this case Haskell 'type' makes type synonym for the type: [a] -> [(b, [a])] In order not to get out of my mind I start thinking about 'type' as a macro substitution mechanism. Then I do this substitution *myself as a Haskell runtime* and get in the result the following declaration of a * real function that Haskell runtime* works with: Succeed :: b -> [a] -> [(b, [a])] Great! This last declaration matches perfectly with function definition: succeed val inp = [(val, inp)] So I start feeling better, after all, it looks like my understanding of Haskell function declarations is not flawed too much. Well, but here comes my main questions! So: 1. Should I work every time as a macro translator when I just see *!any!* function declaration? 2. Should I search through main and imported modules for treacherous 'type' constructs? 3. Where, in this case goes implementation abstraction principle? Why I must provide *all* the details about function argument type structure in order to understand how this function works? Another example of a similar function from the book is: alt :: Parse a b -> Parse a b -> Parse a b alt p1 p2 inp = p1 inp ++ p2 inp In function definition I see three parameters: p1 – matches with function declaration perfectly p2 – matches with function declaration perfectly inp – how to match this parameter with function declaration ? I can match 'inp' parameter with 'alt' function declaration *only* after working as macro processor that expands type synonym 'Parse a b' into '[a] -> [(b, [a])]' and getting *real* declaration: alt :: [a] -> [(b, [a])] -> [a] -> [(b, [a])] -> [a] -> [(b, [a])] with that matches alt p1 p2 inp = p1 inp ++ p2 inp where 'inp' matches with *last* '[a]' argument. It seems that life of "human macro processor" becomes really hard when not trivial functions with 'type' synonym arguments come into play! Where I am wrong? Please enlighten me; I am really at a loss! And thanks for reading all this! Below I give a code example of these functions. Thanks, Dima module Parser where import Data.Char type Parse a b = [a] -> [(b, [a])] none :: Parse a b none inp = [] succeed :: b -> Parse a b succeed val inp = [(val, inp)] suc:: b -> [a] -> [(b, [a])] suc val inp = [(val, inp)] spot :: (a -> Bool) -> Parse a a spot p [] = [] spot p (x:xs) | p x = [(x, xs)] | otherwise = [] alt :: Parse a b -> Parse a b -> Parse a b alt p1 p2 inp = p1 inp ++ p2 inp bracket = spot (=='(') dig = spot isDigit t1 = (bracket `alt` dig) "234"

4 3

Re: [Hs-Generics] FW: [Haskell-cafe] SYB vs HList (again)
by oleg＠pobox.com 22 Mar '07

22 Mar '07

[Please follow-up to generics(a)haskell.org] S. Alexander Jacobson wrote: > HLists require you to define Labels and basically only use label > values that are themselves either scalar or HLists. > ... > With SYB you create field labels using newtype (or data) declarations > e.g. > > data Salary = S {salary::Float} > > With HList, label declarations are really verbose e.g. > > data SalaryLabel deriving(Typeable) > type Salary = Field (Proxy SalaryLabel) Int > salary = proxy :: Proxy FooLabel Actually there is no requirement that HList record names must be scalar `labels', must be Proxies and require such a complex declaration. From HList's high point of view, any collection can be a record provided the type of each item is unique and there is some way to extract the value associated with that type. The HList library provides two implementations of Records (and there was one more, obsolete now). There could be more. For example, I have just committed a yet another implementation, http://darcs.haskell.org/HList/src/RecordD.hs Here a record is a list of things that have a type and a value and provide a way to extract that value. The example from the end of this file seems worth quoting: > data Name = Name String String deriving Show > newtype Salary = S Float deriving Show > data Dept = D String Int deriving Show > > person = (Name "Joe" "Doe") .*. (S 1000) .*. (D "CIO" 123) .*. emptyRecord > > -- could be derived automatically, like Typeable... > instance Fieldish Name (String,String) where > fromField (Name s1 s2) = (s1,s2) > instance Fieldish Salary Float where > fromField (S n) = n > instance Fieldish Dept (String,Int) where > fromField (D s n) = (s,n) > > test1 = show person > -- When a field acts as a label, only its type matters, not the contents > test2 = person .!. (Name undefined undefined) > test3 = person .!. (undefined::Salary) > test5 = person .!. (D "xxx" 111) > I don't know exactly how HList handles default values but I assume you > can restrict use of those values to explicit deserialization contexts. > Is that correct? I'm not sure what you mean about the restriction of default values to deserialization contexts. Anyway, HList provides a left-biased union of two records: hLeftUnion r1 r2 is the record r1 augmented with all the fields from r2 that didn't occur in r2. One may consider r2 to be the record with default fields and the corresponding values. > It would be really nice if there was some way to tell Haskell that > HLists have no more fields than the ones you happen to be getting and > setting in your code. Effectively that would mean you get data > structure inference not just function type inference which would be > really cool! I'm not sure I follow. Could you outline an example of the code you wish work? Incidentally, a lot of the library depends on the record types being members of some specific classes. One can define > newtype ClosedRecord = ClosedRecord r To make a ClosedRecord to be a record from which we can extract the values of some fields, we merely need to say > instance HasField l r v => HasField l (ClosedRecord r) v > where hLookupByLabel l (ClosedRecord r) v = hLookupByLabel l r v Since we did not make this record the member of HExtend or HAppend, it is not extensible.

3 3

How do I do conditional tail recursion in a monad?
by DavidA 22 Mar '07

22 Mar '07

Hi, I would like to write a function untilM, which would be to until as mapM is to map. An example use would be if I had a function dice :: State Int Int which returns random dice throws within a state monad. Then I'd like to be able to do something like untilM (\(s,p)-> s>=100) f (0,1) where f (s,p) = do d <- dice return (s+d, p*d) This should throw dice until the sum exceeds 100, and keeping track of the product as we go along. The problem is that I get stuck trying to manage the interaction of the conditional and the recursion in untilM. Let's start with until: until p f x = if p x then x else until p f (f x) So I figure untilM should look something like: untilM :: Monad m => (a -> Bool) -> (a -> m a) -> a -> m a untilM p f x = return (if p x then x else untilM p f (f x)) The problem is that the two branches of the conditional have different types. If I try to remedy that by changing "then x" to "then return x", it still isn't happy. (My real question is, how do I do conditional tail recursion in a monad?) Thanks in advance.

6 9

Newbie vs. laziness
by Alex Queiroz 21 Mar '07

21 Mar '07

Hallo list, I don't quite get how ($!) works. I have this function: dbCreateIndices con dtn dof = do let dummy = newDbItem let query = "SELECT id FROM " ++ (dtn dummy) ++ " ORDER BY " ++ (dof dummy) ids <- liftM (map fromSql . concat ) $! quickQuery con query [] return $ IntMap.fromList $ zip ids [0..] quickQuery returns a lazy list of results, and I expected ($!) to make it strict. But my program crashes if I use it this way. But, if I add a print to the function: dbCreateIndices con dtn dof = do let dummy = newDbItem let query = "SELECT id FROM " ++ (dtn dummy) ++ " ORDER BY " ++ (dof dummy) ids <- liftM (map fromSql . concat ) $! quickQuery con query [] print ids return $ IntMap.fromList $ zip ids [0..] print makes the ids list strict and all is well. How is the correct way to use ($!) ? Cheers, -- -alex http://www.ventonegro.org/

4 6