- Haskell-Cafe - Haskell.org

Joy Combinators (Occurs check: infinite type)
by Greg Buchholz 12 Mar '05

12 Mar '05

Recently, while investigating the (non-statically typed) stack-based functional language Joy (http://www.latrobe.edu.au/philosophy/phimvt/joy.html) I became interested in seeing if I could implement Joy's combinators in Haskell. I started with a stack based implementation using nested tuples as the stack. Things worked out well until I got to the recursion combinators. Even then, things didn't seem that bad, since Haskell was able to infer types for the the linrec and genrec combinators. Trouble popped up when I tried to apply the recursion operators to a function (in this case calculating the humble factorial). In the code below, fact3,4 & 5 all fail with an "Occurs check" that looks something like the following... joy3.hs:24: Occurs check: cannot construct the infinite type: t = (a, t) Expected type: ((a5 -> (a, (a, t)), a5) -> (a, t), ((a1, t3) -> (a1, (a1, t3)), ((a2, t2) -> (a2, t2), ((a3, t1) -> (Bool, t1),a4)))) -> c Inferred type: ((a5 -> (a, (a, t)), a5) -> (a, (a, t)), (a5 -> a5, (a5 -> (a, (a, t)), (a5 -> (Bool, b),a5)))) -> (a, (a, t)) ...Normally, I would have given up and declared that Joy wasn't an easily typed language, but I'm motivated to dig further because if you remove the type signature from "fact" below, it also fails with an "Occurs check". So, can anyone direct me towards more information on exactly what an "Occurs check" is, or does anyone see an easy fix to my problems? Thanks, Greg Buchholz P.S. The first thing you should note about the code below is the definition of the reverse composition operator (!), which I used to give the program a more Joy-like feel. (i.e. (!) f g = g.f) >--Joy combinators in Haskell > >main = do print $ ((lit 6) ! fact) bot -- factorial of 6 > print $ ((lit 2) ! square ! fact2) bot -- factorial of 4 > >bot = "EOS" -- end of stack >square = dup ! mult >cube = dup ! dup ! mult ! mult > >--In Joy: factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte >fact :: (Integer, a) -> (Integer, a) >fact = (quote ((lit 0) ! eq)) ! > (quote (pop ! (lit 1))) ! > (quote (dup ! (lit 1) ! sub ! fact ! mult)) ! > ifte > >--In Joy: [1 1] dip [dup [*] dip succ] times pop >fact2 = (quote ((lit 1) ! (lit 1))) > ! dip ! (quote (dup ! (quote mult) ! dip ! suc)) > ! times ! pop > >{- fact3,4 & 5 don't type check, fails with... >-- Occurs check: cannot construct the infinite type: > >--In Joy: [null] [succ] [dup pred] [i *] genrec >fact3 :: (Integer, a) -> (Integer, a) >fact3 = (quote nul) ! (quote suc) ! (quote (dup ! pre)) ! (quote (i ! mult)) > ! genrec > >fact4 :: (Integer, a) -> (Integer, a) >fact4 = genrec.quote(mult.i).quote(pre.dup).quote(suc).quote(nul) > >--In Joy: [null] [succ] [dup pred] [*] linrec >fact5 :: (Integer, a) -> (Integer, a) >fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec > >--} >nul = (lit 0) ! eq >suc = (lit 1) ! add >pre = (lit 1) ! sub > >linrec (rec2, (rec1, (t, (p, stack)))) > | fst (p stack) == True = (t stack) > | otherwise = rec2 (linrec (rec2, (rec1, (t, (p, (rec1 stack)))))) > >genrec (rec2, (rec1, (t, (b, stack)))) > | fst (b stack) == True = (t stack) > | otherwise = (rec2.quote(genrec.quote(rec2).quote(rec1). > quote(t).quote(b))) (rec1 stack) > >times (p, (n, stack)) | n>0 = times (p, (n-1, (p stack))) > | otherwise = stack > >(!) f g = g.f >i (a, b) = (a b) >add (a, (b, c)) = (b+a, c) >sub (a, (b, c)) = (b-a, c) >mult (a, (b, c)) = (b*a, c) >swap (a, (b, c)) = (b, (a, c)) >pop (a, b) = b >dup (a, b) = (a, (a, b)) >dip (a, (b, c)) = (b, (a c)) >eq (a, (b, c)) | a == b = (True, c) > | otherwise = (False,c) > >ifte (f, (t, (b, stack))) | fst (b stack) == True = (t stack) > | otherwise = (f stack) > >lit val stack = (val, stack) -- push literals on the stack >quote = lit >

5 19

Card trick
by Mark Carroll 11 Mar '05

11 Mar '05

Having heard about an interesting card trick, I thought I'd try implementing it in Haskell. With luck, I didn't make any mistakes. I thought it was cool enough to be worth sharing with you guys. -- Mark

1 0

Problem with Haddock
by Daniel Fischer 09 Mar '05

09 Mar '05

Hi, I have the problem that I can't haddock literate modules (latex-style), > haddock -h -o docs Test.lhs Test.lhs:1:1: Parse error the file begins with "\begin{code}". Does anybody know what's up and what to do about it? Furthermore, in the documentation of ghc-6.4.2005..., only four modules from base/GHC are included, in the documentation for ghc-6.2.2 there were 29. In particular, the absence of GHC.List, GHC.Show and GHC.Read is extremely annoying. Any suggestions how to remedy this? Thanks in advance, Daniel

3 3

RE: [Haskell-cafe] Problem with Haddock
by Simon Marlow 09 Mar '05

09 Mar '05

On 08 March 2005 15:26, Daniel Fischer wrote: > I have the problem that I can't haddock literate modules > (latex-style), >> haddock -h -o docs Test.lhs > Test.lhs:1:1: Parse error > > the file begins with "\begin{code}". > > Does anybody know what's up and what to do about it? Haddock doesn't understand literate files on its own. The documentation describes how to get around this... er, well the documentation in CVS describes how to get around this, but the 0.6 docs on the web don't. Here's the relevant text: <section id="cpp"> <title>Using literate or pre-processed source</title> <para>Haddock only accepts plain, non-literate, Haskell source. This means that if you program in Literate Haskell, or you need to use the C pre-processor in your Haskell source, then you need to pre-process the files before feeding them to Haddock. This is easily accomplished using GHC; for example, suppose we have a Literate Haskell source file <filename>Foo.lhs</filename>, on which we also need to run the C pre-processor:</para> <screen> $ ghc -cpp -E -optP-P -D__HADDOCK__ Foo.lhs -o Foo.hs $ haddock -h Foo.hs ... </screen> <para>The <option>-E</option> option to GHC says "stop after pre-processing", the <option>-cpp</option> option turns on the C pre-processor, the <option>-optP-P</option> option tells the C pre-processor not to leave any extra dropping behind (see the description of the <option>-P</option> option in the gcc manual for details), and the <option>-D__HADDOCK__</option> option defines the symbol <literal>__HADDOCK__</literal> when pre-processing (this is sometimes handy if you need to any pre-processing conditionals in your source which depend on whether the source is going to be fed to Haddock).</para> </section> Cheers, Simon

1 0

tuples and Show in GHC
by Stijn De Saeger 08 Mar '05

08 Mar '05

hi all, Is there a principled reason why in GHC tuples with up to five elements automatically derive from the Show class but from six elements and up they don't anymore? If this is not a bug I would be very curious to hear what the reasoning behind this is.... below is an example of said behaviour : > type MyInt1 = (Int,Int,Int,Int,Int) > myInt1 :: MyInt1 > myInt1 = (1,2,3,4,5) > type MyInt2 = (Int,Int,Int,Int,Int,Int) > myInt2 :: MyInt2 > myInt2 = (1,2,3,4,5,6) .... *HS> myInt1 Loading package haskell98 ... linking ... done. (1,2,3,4,5) *HS> myInt2 <interactive>:1: No instance for (Show MyInt2) arising from use of `print' at <interactive>:1 In a 'do' expression: print it *HS> stijn.

5 5

RE: [Haskell-cafe] tuples and Show in GHC
by Simon Peyton-Jones 07 Mar '05

07 Mar '05

No principled reason. I wish there was no limit, which would involve generating code on the fly for instances that weren't pre-generated, but I never got around to implementing that. So you have to stop somewhere. Actually the Report says it should have Show instances up to 15 at least, but GHC doesn't. That isn't deliberate, and I guess we should fix it. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Stijn | De Saeger | Sent: 06 March 2005 09:40 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] tuples and Show in GHC | | hi all, | | Is there a principled reason why in GHC tuples with up to five | elements automatically derive from the Show class but from six | elements and up they don't anymore? If this is not a bug I would be | very curious to hear what the reasoning behind this is.... | below is an example of said behaviour : | | > type MyInt1 = (Int,Int,Int,Int,Int) | > myInt1 :: MyInt1 | > myInt1 = (1,2,3,4,5) | > type MyInt2 = (Int,Int,Int,Int,Int,Int) | > myInt2 :: MyInt2 | > myInt2 = (1,2,3,4,5,6) | | .... | | *HS> myInt1 | Loading package haskell98 ... linking ... done. | (1,2,3,4,5) | *HS> myInt2 | | <interactive>:1: | No instance for (Show MyInt2) | arising from use of `print' at <interactive>:1 | In a 'do' expression: print it | *HS> | | stijn. | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

ANN: HAppS -- Haskell Application Server v 0.3
by S. Alexander Jacobson 05 Mar '05

05 Mar '05

HAppS is a Haskell library for building Internet applications, featuring: * HAppS.ACID: Guarantee application integrity in the face of unplanned outages using this module's integrated write-ahead logging and checkpointing framework. * HAppS.DBMS: Do relational operations in Haskell (rather than SQL) on Haskell sets (outside the IO Monad). Define custom indices for your Haskell datatypes (e.g. geographic/geometric types). Use in combination with ACID for a robust relational DBMS customized for your application. * HAppS.Protocols: Expose your application using as an HTTP server and/or by recieving and sending SMTP. Changes since 0.2: HAppS Changes * Much cleaner interface for ACID transaction handlers * DBMS operators that look more like HaskellDB operators * SMTP send errors are exposed for use in future reliable deliver implementation * ACID callbacks disabled. Framework in place for total order on callbacks. * SideEffect queues are now algrebraic types rather than strings. * Parametrized HTTP using XML ToElement and HTTP ToMessage FromMessage and ToURI classes (you write transaction handlers in terms of Haskell types and the system takes care of exposing them for HTTP) * Parametrized HTTP response now has type (ToURL url,ToMessage msg)=>Response url message Framework takes care of automatically translating relative URLs to absolute URLs. Answers to questions a few people have asked: * Compare HAppS.DBMS with HaskellDB HaskellDB is really optimal if you want to talk to external databases. HAppS.DBMS is really good if you want to do relational operations on Haskell Sets without going to the IO monad. * Compare HAppS.ACID to STM Use STM if all your IO operations have a two-phase-commit interface. Use HAppS.ACID if your IO interfaces are not transactional. Instead HAppS.ACID gives you multi-queue, at-least-once execution of side-effects, and a total order on their callbacks. There is no rollback semantic because you can't unsend email. * Compare HAppS.Protocols.SMTP to Peter Simon's Postmaster Postmaster is trying to be a full fledged MTA. SMTP is trying simply to give you SMTP receive/send functionality in your applications. Neither yet has a queuehandler. We both hope to merge lessons learned soon. * Compare HAppS.Protocols.HTTP to Warrick Gray's Network.HTTP module Network.HTTP is more oriented towards building HTTP clients. HAppS..HTTP is more oriented towards building HTTP servers. Network.HTTP enforces a stronger separation between headers and body. HAppS..HTTP delivers a MIME message back to the app. With infrastructure to enable transparent conversion to and from application datatypes. -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

1 0

State Monad
by Derek Elkins 05 Mar '05

05 Mar '05

> Thinking of stacks, I've often wondered if Haskell would be a good > language for implementing a PostScript interpreter. I actually have the beginning of a PostScript interpreter somwhere... And the core of a Joy interpreter is extremely small. It's pretty much 'foldl compose . map interpretWord'. Of course, I implemented a Joy interpreter in the slightly sugared lambda calculus that lambdabot's @eval module supports so... (Crap, I actually want to find it (the PostScript interpreter) now.)

1 0

State Monad
by Sam G. 04 Mar '05

04 Mar '05

I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime. Could you help me writing this monad? To start, I just need a + function which will return the sum of the 2 toppest elements of the stack. Thanks in advance, Sam.

5 6

Corba and Haskell
by Maurício 04 Mar '05

04 Mar '05

Hi, Have you guys used any Corba library for Haskell? Which one would you recommend (if there are more than one)? Thanks, Maurício

1 0