February 2007 - Haskell-Cafe

Illegal polymorphic or qualified type: forall l.
by Marc Weber 25 Feb '07

25 Feb '07

how can i fix this? Mmmh I really need some haskell type class traingings ;) ============= test file ============================================== module Main where import HList import HOccurs import Control.Monad.Reader class Get a b where get :: a -> b data D1 = D1 Int -- dummy type type ActionMonad a l = forall l. (HOccurs D1 l) => ( ReaderT l IO a ) data CR = CR (ActionMonad Bool ()) instance Get CR (ActionMonad Bool ()) where get (CR a) = a main = do print "test" ============= error ================================================== || [1 of 1] Compiling Main ( uqt.hs, uqt.o ) || uqt.hs|16| 0: || Illegal polymorphic or qualified type: forall l. || (HOccurs D1 l) => || ReaderT l IO Bool || In the instance declaration for `Get CR (ActionMonad Bool ())' ====================================================================== Marc

2 2

newbie question about denotational semantics
by Alexander Vodomerov 25 Feb '07

25 Feb '07

Hi all! I'm just started learning denotational semantics and have a simple question. Suppose, we have simple language L (e.g. some form of lambda-calculus) and have a semantic function: E : Term_L -> Value. Now, suppose, we extended our language with some additional side-effects (e.g. state or continuations). For this purpose we first add new syntactic construct to language (e.g 'call/cc'), and then write semantic via monadic approach. We have: L_ext = L + 'call/cc' E_ext : Term_{L_ext} -> M (Value), where M is some monad (Cont Value for our case). Now, I want to proof statement that original and extended semantics are coincide on expressions that don't use new constructs (call/cc). It would be natural to formulate such "theorem": "Theorem". If t is expression, that doesn't use new construct, then E_orig(t) = E_ext(t). Alas, this equation doesn't make any sense, because E_orig(t) and E_ext(t) are elements of different domains: Value and M(Value). The obvious "fix" it to use "unit" operation of monad ("return" in Haskell syntax) to put both values into the same space. So we get: "Theorem" (second try). For all t, bla-bla-bla.. unit_M(E_orig(t)) = E_ext(t). However, this still doesn't work because Values are in fact different: -- in original semantic we have (more source code available below) data Value1 = Number Int | Func (Value1 -> Value1) -- in extended semantic we have data Value2 = Number Int | Func (Value2 -> M Value2) ^ note this M The monad M seems to be "wired in" recursively in Value definition. >From the mathematical point of view it is common to use projection or injection when one need to compare functions to different sets. However, I don't see any obvious injection Value1 -> Value2 or projection Value2 -> Value1. Some monads can be "removed", for example StateT can be eliminated with runState with initial state and etc. However, some monads, for example Error, Maybe, non-deteminism monad (powerdomain) don't have such "removal function". What is needed is general definition that can be used for _any_ monad M. The question is: how can this "theorem" be formulated (and prooved) in mathematically precise way? It seems that I missing something very trivial, so just reference to article will be nice. The more general question is: suppose original language already has side-effects and was described using monad M_1. Now we add additional effects and use bigger monad M_2. The same question arises: how one can compare elements in Value domain defined via M_1 and M_2? With best regards, Alexander. PS. Some code I played with: -- original semantic import Control.Monad.Reader import Control.Monad.State import qualified Data.Map as Map type Id = String type Env = Map.Map String Value stdops :: Map.Map String (Int -> Int -> Int) stdops = Map.fromList [("+", (+)), ("-", (-)), ("*", (*))] data Expr = Const Int | Var String | BinOp String Expr Expr | Lambda Id Expr | Appl Expr Expr deriving Show data Value = Number Int | Func (Value -> Value) instance Show Value where show (Number v) = show v show (Func _) = "*func*" eval :: Expr -> Reader Env Value eval (Const c) = return (Number c) eval (Var i) = do env <- ask return $ env Map.! i eval (BinOp op x y) = do vx <- eval x vy <- eval y let opfun = stdops Map.! op case (vx, vy) of (Number a, Number b) -> return $ Number (opfun a b) _ -> error "standard operation on not-numbers" eval (Lambda i expr) = do env <- ask let f = \v -> let newenv = Map.insert i v env in runReader (eval expr) newenv return (Func f) eval (Appl fun arg) = do vfun <- eval fun varg <- eval arg case vfun of Func f -> return $ f varg _ -> error "application of not-function" do_eval :: Expr -> Value do_eval expr = runReader (eval expr) Map.empty -- extended semanic import Control.Monad.Reader import Control.Monad.Cont import qualified Data.Map as Map type Id = String type Env = Map.Map String Value type M = Cont Value stdops :: Map.Map String (Int -> Int -> Int) stdops = Map.fromList [("+", (+)), ("-", (-)), ("*", (*))] data Expr = Const Int | Var String | BinOp String Expr Expr | Lambda Id Expr | Appl Expr Expr | CallCC Expr deriving Show data Value = Number Int | Func (Value -> M Value) instance Show Value where show (Number v) = show v show (Func _) = "*func*" eval :: Expr -> ReaderT Env M Value eval (Const c) = return (Number c) eval (Var i) = do env <- ask return $ env Map.! i eval (BinOp op x y) = do vx <- eval x vy <- eval y let opfun = stdops Map.! op case (vx, vy) of (Number a, Number b) -> return $ Number (opfun a b) _ -> error "standard operation on not-numbers" eval (Lambda i expr) = do env <- ask let f = \v -> let newenv = Map.insert i v env in runReaderT (eval expr) newenv return (Func f) eval (Appl fun arg) = do vfun <- eval fun varg <- eval arg case vfun of Func f -> lift $ f varg _ -> error "application of not-function" eval (CallCC expr) = do f <- eval expr case f of Func vf -> lift $ callCC (\k -> vf (Func k)) _ -> error "call/cc with not-function" do_eval :: Expr -> Value do_eval expr = runCont (runReaderT (eval expr) Map.empty) id

3 3

How to build a generic spreadsheet?
by Greg Fitzgerald 24 Feb '07

24 Feb '07

I want to write a program where a user would update a bunch of variables, and everything that depends on those variables (and nothing else) are recalculated. Basically, a spreadsheet, but generalized for any computation. Could someone recommend an elegant way to do it or some good reading material? Thanks, Greg

6 8

Need help of explanation possible!!! Pls
by iliali16 24 Feb '07

24 Feb '07

Hi I am abit new to this language though I manage to study it very fast and understand it well. I have some tutorials to do inorder to practice it. The thing is I want to declear some functions but to do that I need to understand how exactly "take" works in hugs. Couse I want to build a similar function but I don't know how I will continue: this is where I reach take :: Integer -> [Integer] -> [Integer] take _ [] = [] take n xs |x < lenghtList xs = (take (n-1) xs :[]) |otherwise = xs I have decleared lenghtList before. I am not going to discuse lenght now couse it is easy and not for the scope of what I need. I know that what I did up there is completly wrong but that is what I came out while trying to understand how would the interpreter read and implement this. If you have any ideas how this function works please explain me I would be very greatfull.I have to do a similar one but to do it I have to understand this one. If u try it in hugs u will realise it is an allready decleared function but what I need is to understand how it works.What it must do is to get a num and a list and to display the elements of the list till the nth element which is the number we have given.if the list is smaller in lenght then the given num we return the whole list. Thanks in advance to all the folks who do help me please :(( ! -- View this message in context: http://www.nabble.com/Need-help-of-explanation-possible%21%21%21-Pls-tf3282… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

Embedding ghc
by Brian Smith 24 Feb '07

24 Feb '07

"If you have to ask, you can't afford it." :) The GHC API is not modular--if you use it, then the entirety of GHC is included into your program. That means that your executable will increase by the size of ghc.exe. Furthermore, you will also need to ship several of the supporting executables, alongside the result. Basically, using the GHC API is going to add nearly the entire size of the full GHC distribution to your application. On Windows, If you don't use via-C code generation, then you might be able to cut out some parts of the embedded GCC distribution (libraries, etc.) I once looked at modularizing GHC so that parts like the bytecode interpreter, via-C compilation, template haskell, and compilation to/from external core could be removed to reduce the size of the program. However, it is non-trivial to do this, and I didn't want to maintain a branch of GHC with these parts factored out. it would be better to come up with a proposal that the GHC maintainers will accept for the mainline, and then implement it, if you want a modular GHC. I would like to do so but currently I am busy on other projects. - Brian On 2/10/07, Joel Reymont <joelr1(a)gmail.com> wrote: > > Has anyone tried embedding ghc into their app? > > How big are the resulting binaries? > > Thanks, Joel > > -- > http://wagerlabs.com/ > > > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

Extracting structured data in XML into records
by Johan Tibell 24 Feb '07

24 Feb '07

Hi! I'm trying to extract HCards (http://microformats.org/wiki/hcard) from HTML documents. HCard is a microformat. Microformats is an attempt to add semantic information to XML documents without adding any new tags. This is done by adding semantic information in class attributes instead (see the 'testXml' string below). I'm trying to find a good way to extract HCards into Haskell records. To do this I need to map XML elements with certain attribute values onto record fields. Some of the elements are optional in the XML and I represent that using Maybe fields in my record. The order of the elements is not guaranteed only the way they are nested. This makes it more difficult to first extract the fields I want into a list of Strings and then map that onto my record since I need to tag each string with the value it represents. So my question is. How can I write the function 'extractElementsIntoRecords' below. Or, perhaps HXT is the wrong tool for the job and I should be trying to walk the DOM tree instead? > module HCard where > > import Text.XML.HXT.Arrow > > data HCard = HCard > { > familyName :: String, > givenName :: String > org :: Maybe String > url :: Maybe String > } deriving Show > > parseHCards xml = runX $ parseXml xml > > parseXml xml = > readString [(a_parse_html, v_1)] xml >>> > deep (hasClassName "vcard") >>> > extractElementsIntoRecords > > extractElementsIntoRecords = undefined > > hasClassName s = hasAttrValue "class" (elem s . words) > > testXml = > "<div class=\"vcard red\">" ++ > " <a class=\"url\" href=\"http://tantek.com/\">" ++ > " <span class=\"n\" style=\"display:none\">" ++ > " <span class=\"family-name\">Çelik</span>" ++ > " <span class=\"given-name\">Tantek</span>" ++ > " </span>" ++ > " <span class=\"fn\">Tantek Çelik</span>" ++ > " </a>" ++ > " <div class=\"org\">" ++ > " <span class=\"organization-name\">Technorati</span>" ++ > " </div>" ++ > "</div>" > > main = parseHCards textXml Cheers, Johan Tibell

2 1

Re: Code and Perf. Data for Prime Finders
by oleg＠pobox.com 24 Feb '07

24 Feb '07

Perhaps you might want include in your test the following: http://www.haskell.org/pipermail/haskell-cafe/2007-February/022437.html It seems quite close to the genuine Eratosthenes sieve algorithm: it employs the idea of marks, it can cross composite numbers off several times, and it never tries to divide or examine prime numbers. In fact, the algorithm doesn't even use the full division or full comparison (let alone other arithmetic operations).

1 0

beginner question re example in Hutton's "Programming in Haskell"
by David Cabana 23 Feb '07

23 Feb '07

I have been trying to work through Graham Hutton's "Programming in Haskell", but have hit something of a snag in chapter 8.4. Hutton presents some sample code which I am trying to run, with no luck so far. Here is the code as I constructed it by gathering snippets presented across three pages. <code> module Main where -- as per Hutton page 75 type Parser a = String -> [(a, String)] -- page 75 return :: a -> Parser a return v = \inp -> [(v,inp)] -- page 76 failure :: Parser a failure = \inp -> [ ] item :: Parser Char item = \inp -> case inp of [ ] -> [ ] (x:xs)-> [(x,xs)] parse :: Parser a -> String -> [(a,String)] parse p inp = p inp -- page 77 p :: Parser (Char, Char) p = do x <- item item y <- item return (x,y) </code> When I tried to load this code, I got this error message: Ambiguous occurrence `return' It could refer to either `return', defined at /Users/joe/haskell/ parse2.hs:8:0 or `return', imported from Prelude OK. My reasoning was that Hutton took the trouble to define return, so I decided to use the local definition instead of the one in the Prelude. I changed the last line from "return (x,y)" to "Main.return (x,y)". The new error message is worse: Couldn't match expected type `Char' against inferred type `[(Char, String)]' In the expression: x In the first argument of `return', namely `(x, y)' In the expression: return (x, y)</blockquote> Hutton provided explicit type signatures, so I did not expect type issues. I decided to take another approach. The book has a website that lists errata and provides code listings. The code for chapter eight is at http://www.cs.nott.ac.uk/~gmh/Parsing.lhs When I read Hutton's code, I noticed that he begins by importing Monad. The code I list above is from chapter 8, pages 75-77 of the book. Monads have not yet been mentioned. The book's index shows that monads aren't mentioned till page 113, in chapter 10. I also notice that in his code, Hutton makes repeated use of a symbol P whose meaning I do not know. What do I have to do to make this code work? I know I can use Hutton's code from the website, but I expected the code presented in the book to work, or the code on the website to restrict itself to what has been discussed in the book. Am I missing something here? Thanks, David Cabana

2 1

Re: [Haskell-cafe] A "real" Haskell Cookbook
by P. R. Stanley 23 Feb '07

23 Feb '07

>>As a tip for anyone involved in writing and publishing scientific >>materials on the web, unless the maths is either written without any >>funny symbols or, better still, typeset in latex, it is not >>accessible to a screen-reader. > >I was under the impression that modern screen readers could pronounce >Unicode characters by looking up their name. I.e., your   would >get read as 'Non-breaking space' (perhaps a bad example, this one >wouldn't want to be read out due to its abuse as a layout tool, which >would make reading old pages very awkward). > >I don't see how images are going to be much better? I suppose <math> >images do, on MediaWiki, have an alt text which is their LaTeX, but >I'd hate to have to have that read to me. > I think latex is the perfect solution to the problem. It is > perhaps the only 100 percent accessible medium available right now. > It doesn't require any special software to read. All it needs is a > simple text editor. >Latex is a well-established tool/medium in the world-wide scientific >community and therefore its inclusion in the Haskell wikibook or any >other scientific document along with the unicode characters and >image files would be potentially beneficial to everyone. Paul >If you're interested in talking to the authors of the wikibook, >subscribe to the wikibook(a)haskell.org mailing list. > >-- >-David House, dmhouse(a)gmail.com

1 0

Re: [Haskell-cafe] A "real" Haskell Cookbook
by P. R. Stanley 23 Feb '07

23 Feb '07

Andrew and co, I have a big fat apology to make. It was actually the wikipedia page on Lambda Calculus where there are many occurrences of special symbols. The Wikibook, as far as I've explored, is fully accessible. Nonetheless, I'd still be more than happy to make my contributions in any way I can. I am a beginner to functional programming and so I could play a useful role in ensuring the text takes nothing for granted with regard to the fundamental principles and beyond. As a tip for anyone involved in writing and publishing scientific materials on the web, unless the maths is either written without any funny symbols or, better still, typeset in latex, it is not accessible to a screen-reader. One small point about the Haskell source code is that the column indentations do not always appear in the screen reader browse buffer. Of course, there are ways of getting around the issue and if the author of the Wikibook is interested we could discuss the details off list. Cheers, Paul At 16:22 22/02/2007, you wrote: >Can you guys point out an example of this in the wiki book? I've never >heard of this accessibility issue. I may even be willing to go back >through and modify the wikibook to make it more accessible of you can >explain what you're referring to. Accessibility is important to me. > >On 2/21/07, P. R. Stanley <prstanley(a)ntlworld.com> wrote: >>and can I please ask anyone thinking of using special symbols to >>resist the temptation. >>Symbols such as the &160 used liberally in the Haskell wikibook are >>totally invisible to screen readers. >>I would be happy to proof read any document before it goes to the >>wikibook to ensure it's fully accessible to screen readers. >> >>Regards, >>Paul >> >>At 03:17 22/02/2007, you wrote: >> >I made a preliminary page, and fleshed out some of the >> >headers/sub-headers on the wiki page for a good Haskell Cookbook >> >(aka NOT a PLEAC clone). Please contribute and/or fix the examples >> >and explanations so we can make a really nice Cookbook for newbies. :) >> > >> > http://haskell.org/haskellwiki/Cookbook >> > >> >_______________________________________________ >> >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

4 3