- Haskell-Cafe - Haskell.org

A "real" Haskell Cookbook
by Martin Bishop 26 Feb '07

26 Feb '07

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

9 13

Memoisation
by Tony Morris 26 Feb '07

26 Feb '07

I have a backtracking algorithm that I need to memoise with. Rather than go into the intricacies of the algorithm, I figure (and hope) the factorial function is trivial enough to point out my problem. Simply, suppose I wish to calculate the factorial of 10, then "later" the factorial of 5. I have already calculated the factorial of 5, but now I must do it again. I have thought of various ways of preventing this; perhaps passing an Array in a state monad. I'm wondering if there is a general solution for this kind of problem. Thanks for any tips. -- Tony Morris http://tmorris.net/

3 2

How to build a python module using Haskell?
by Albert Lee 25 Feb '07

25 Feb '07

I have found some docs about build Windows DLL using Haskell and then using ctypes from python. But how to do this on Linux/FreeBSD ?

2 1

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