- Haskell-Cafe - Haskell.org

Re: Leaves of a Tree
by Chad Scherrer 22 Feb '07

22 Feb '07

Tom, I think inserting elements would be a lot faster than multiple unions. I would try: leafList :: Tree -> [Int] leafList (Leaf n) = [n] leafList (Branch left right) = leafList left ++ leafList right leaves = fromList . leafList If you're writing many functions on Trees (or maybe even if you're not), you might consider writing a fold function and putting leafList in terms of this. Do you have experience with folds? -Chad > Hello, > > Any recommendations for speeding up extracting the set of leaves from a tree? > > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > > My slow, naive function: > > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) > > In my case, many of the branches in the tree are the same. I suspect > the fixed point operation mentioned in the thread "speeding up > fibonacci with memoizing" is applicable, but I'm having a tough time > making the connection. > > -Tom

2 1

Type-level lambdas in Haskell?
by oleg＠pobox.com 22 Feb '07

22 Feb '07

On 2/21/07, Alfonso Acosta <alfonso.acosta at gmail.com> wrote: > In my opinion adding Type-level lambdas would be the way to go, but > they unfortunately are not part of Haskell. Type-level lambdas are already present in Haskell. Please see the messages On computable types. I. Typed lambda and type closures http://www.haskell.org/pipermail/haskell/2006-September/018486.html On computable types. II. Flipping the arrow http://www.haskell.org/pipermail/haskell/2006-September/018487.html

1 0

Type-level lambdas in Haskell? ( was Multiparameter class error)
by Alfonso Acosta 22 Feb '07

22 Feb '07

Now I'm facing another problem, sorry if it takes too long to reach the Type level lambdas issue ... The full definition of my class is class Synchronous s f1 f2 | s -> f1, s -> f2 where mapSY :: f1 a b -> s a -> s b delaySY :: a -> s a -> s a zipWithSY :: f2 a b c-> s a -> s b -> s c The goal of this class is to extend the name of the following functions (which BTW are already present in a working library and for that reason _it is a must_ that their types remain untouched) ... mapSY :: (a->b) -> Signal a -> Signal b delaySY :: a -> Signal a -> Signal b -> Signal c zipWithSY :: (a->b->c) -> Signal a -> Signal b -> Signal c .. accepting these definitions as well mapSY :: (HDPrimType a, HDPrimType b) => HDFun (a->b) -> HDSignal a -> Signal b delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a zipWithSY :: (HDPrimType a, HDPrimType b, HDPrimType c) => HDFun (a->b->c) -> HDSignal a -> HDSignal b -> HDSignal c The problem is: How to choose the f1 and f2 parameters when defining the instances? instance Synchronous Signal (->) ?? where instance Synchronous HDSignal ?? ?? where I'm facing one of the problems discussed at Type Classes with Functional Dependencies (http://web.cecs.pdx.edu/~mpj/pubs/fundeps-esop2000.pdf )section 3.1: "Some of the remaining instances can be reworked to ﬁt the constructor class framework by introducing dummy type and value constructors" The following is a solution following the one proposed by MJones in his paper, but is not acceptable as it requires changing the types of the original functions. newtype F2 a b c = F2 (a->b->c) newtype HDF1 a b = HDF1 (HDFun (a->b)) newtype HDF2 a b c = HDF2 (HDFun (a->b->c)) instance Synchronous Signal (->) F2 where .... instance Synchronous HDSignal HDF1 HDF2 where ... Following MJones advice, redefining the class to something such us ... class Synchronous2 a sa sb sc f1ab f2abc | {- dependencies ommited -} where mapSY :: f1ab -> sa -> sb delaySY :: a -> sa -> sa zipWithSY :: f2abc-> sa -> sb -> sc ... is feasible but not elegant at all because the number of class parameters and dependencies are dramatically increased. In my opinion adding Type-level lambdas would be the way to go, but they unfortunately are not part of Haskell. Something like this would be much more expressive and useful. Using the first definition of the class we could do something as instance Synchronous Signal (->) (\a b c -> (a->b->c)) where .... instance Synchronous HDSignal (\a b -> HDFun (a->b)) (\a b c -> HDFun (a->b->c)) where ... Is there any extension to the language covering type-level lambdas or even a plan to include them in next revision? Thanks, Fons On 2/21/07, Alfonso Acosta <alfonso.acosta(a)gmail.com> wrote: > Thanks, the functional dependency solved the problem > > On 2/21/07, Yitzchak Gale <gale(a)sefer.org> wrote: > > Hi Alfonso, > > > > You wrote: > > > Could not deduce (Synchronous s f11) > > > from the context (Synchronous s f1) > > > \begin{code} > > > class Synchronous s f1 where > > > mapSY :: f1 a b -> s a -> s b > > > delaySY :: a -> s a -> s a > > > sourceSY :: f1 a a -> a -> s a > > > sourceSY f s0 = o > > > where > > > o = delaySY s0 s > > > s = mapSY f o > > > \end{code} > > > > > > Can anyone explain a bit further than GHC what am I doing wrong? > > > > Every method of a multiparameter class must refer > > to every parameter in its signature. Otherwise, there > > is no way for the compiler to know which instance > > of the class you want when you use the method. > > > > There are two ways to get around this restriction. > > One is to use a functional dependency: > > > > class Synchronous s f1 | s -> f1 where > > > > That promises that for each type s, you will > > only define an instance Synchronous s f1 > > for at most a single type f1. Now, whenever > > you mention s in a type signature, it is as if > > you also mentioned f1. > > > > If you can't keep that promise, then you will > > have to use a phantom parameter. Change > > the type of delaySY to > > > > delaySY :: f1 -> a -> s a -> s a > > > > and ignore the f1 parameter when you implement > > delaySY: > > > > delaySY _ x y = ... > > > > Then, when you use delaySY, you specify the > > type f1 by writing: > > > > delaySY (undefined :: T) ... > > > > Regards, > > Yitz > > >

2 1

Saving the AST generated by Template Haskell
by Alfonso Acosta 22 Feb '07

22 Feb '07

Hi all, I'm using Template Haskell to design a small subset of a Hardware Description DSEL (Domain Specific Embedded Language). My language supports higher order as the user can supply small functions as arguments. I chose to parse them with TH because it allows me to use plain Haskell for the function syntax (instead of reinventing the wheel) but mostly because gives parsing for free. The AST of the functions must be kept by the embedded compiler so that it can be later translated to a target language by one of the potential backends of the embedded compiler. The problem is ... how to store that AST? Let me show an example ---- import Language.Haskell.TH.Syntax -- sample function from the DSLE library hdMapSY :: (HDPrimType a, HDPrimType b) => HDFun (a -> b) -> HDSignal a -> HDSignal b -- We keep the function's AST (to make program transformations in the backends) newtype HDPrimFun = HDPrimFun [Dec] deriving Show -- Type safety layer, we keep the function to make sure TH checks the type (and possible further simulations) data HDFun a = HDFun [Dec] a deriving Show -- Helper constructor function, which suffers from the Saving-the-AST problem -- mkMetaAST currently returns a phony value mkHDFun :: Q [Dec] -> Q Exp mkHDFun qd = do dx <- qd metaASTnm <- newName "metaAST" let funnm = getFunName dx metaAST = mkMetaAST dx metaASTdec = ValD (VarP metaASTnm) (NormalB metaAST) [] return $ LetE (metaASTdec:dx) (AppE (AppE (ConE $ mkName "HDFun") (AppE (ConE $ mkName "HDPrimFun") (VarE metaASTnm))) (VarE funnm)) where getFunName :: [Dec] -> Name getFunName [FunD nm _] = nm getFunName _ = error "mkHDFun: toy example, just and exactly one dec!" -- This function should create an AST expression from the AST -- but it would be a big pain to code mkMetaAST :: [Dec] -> Exp mkMetaAST _ = AppE (ConE (mkName "LitE")) (LitE (StringL "big pain to code!")) --- An example program coded in the DSLE could could be something like .. myCircuit :: HDSignal Int -> HDSignal Int myCircuit = hdMapSY ($mkHDFun [d| f input = input+1 |]) So the question is .. How can mkHDfun save the AST of "f input = input+1" (for which it needs to create and return a metaAST) without the effort of having to create boiler plate code for the whole TH library types? Did anyone do something similar before? I workaround would be saving the String of the AST with show, but Dec nor Exp belong to the Read class, :S Thanks in advance, Alfonso Acosta

2 3

Fwd: [Haskell-cafe] Newbie: generating a truth table
by Peter Berry 21 Feb '07

21 Feb '07

Sigh, I seem to have done a reply to sender. Reposting to the list. On 06/02/07, phiroc(a)free.fr <phiroc(a)free.fr> wrote: > Hello, > > I would like to create a Haskell function that generates a truth table, for > all Boolean values, say, using the following "and" function : > > and :: Bool -> Bool -> Bool > and a b = a && b A fairly old thread, but I had an interesting idea: > combos :: (Enum a, Enum b) => a -> b -> (a -> b -> c) -> [(a, b, c)] > combos min1 min2 op = [(x, y, x `op` y) | x <- [min1..], > y <- [min2..]] Then: *Main> combos False (&&) [(False,False,False),(False,True,False),(True,False,False),(True,True,True)] In the case of Bool and a few others, you can use a slightly nicer one: > bCombos :: (Enum a, Bounded a, Enum b, Bounded b) => > (a -> b -> c) -> [(a, b, c)] > bCombos op = [(x, y, x `op` y) | x <- [minBound..maxBound], > y <- [minBound..maxBound]] And: *Main> bCombos (&&) [(False,False,False),(False,True,False),(True,False,False),(True,True,True)] The secret of these is of course in the Enum and Bounded type classes, which define, respectively, * enumFrom and enumFromTo (which have syntactic sugar in [foo..] and [foo..bar] respectively), and * minBound and maxBound. You can do the same with any instance of these classes. -- Peter Berry <pwberry(a)gmail.com> Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html

5 4

Multiparameter class error
by Alfonso Acosta 21 Feb '07

21 Feb '07

Hi, I'm a newbie to multiparameter classes and I'm getting this error from GHC when compiling the following class definition: Could not deduce (Synchronous s f11) from the context (Synchronous s f1) arising from use of `delaySY' Possible fix: add (Synchronous s f11) to the class or instance method `sourceSY' In the expression: delaySY s0 s In the definition of `o': o = delaySY s0 s In the definition of `sourceSY': sourceSY f s0 = o where o = delaySY s0 s s = mapSY f \begin{code} class Synchronous s f1 where mapSY :: f1 a b -> s a -> s b delaySY :: a -> s a -> s a sourceSY :: f1 a a -> a -> s a sourceSY f s0 = o where o = delaySY s0 s s = mapSY f o \end{code} Can anyone explain a bit further than GHC what am I doing wrong? Thanks, Alfonso Acosta

2 2

Implementation of scaled integers
by Stefan Heinzmann 21 Feb '07

21 Feb '07

Hi all, is there a library for Haskell that implements scaled integers, i.e. integers with a fixed scale factor so that the scale factor does not need to be stored, but is part of the type? In particular it would be useful (i.e. for signal processing) to have numbers based on Int scaled such that they fall into the range [-1.0 .. 1.0). Or other scale factors which are powers of 2. Addition and subtraction would then map to the ordinary operations for Int, while Multiplication and Division would have to apply the scale factor to correct the result of normal Int operations (which would be a shift operation). If it doesn't exist yet, have you got ideas how to implement that for maximum efficiency? Cheers Stefan

6 7

nobench: now with hbc support (!)
by dons＠cse.unsw.edu.au 21 Feb '07

21 Feb '07

Just a quick note. I've tweaked the benchmarks some more, adding support for Lennart's hbc compiler. (Go hbc!). Also, we have nice html output (thanks to Text.XHtml!). http://www.cse.unsw.edu.au/~dons/nobench/results.html Pretty :-) Remaining tasks left are to port the rest of the 'real' category from nofib, and implement output diffing (note the nhc winning entries, due to erroneous output), and add nhc's bytestring support. The particular errors are logged here, http://www.cse.unsw.edu.au/~dons/nobench/bench.results -- Don

1 0

Call for testers: using Cabal to build RPMs
by Bryan O'Sullivan 20 Feb '07

20 Feb '07

I've got a branch of Cabal that adds a new command, "rpm", that lets you build an RPM package with a single invocation: runhaskell Setup.*hs rpm I've tested this pretty extensively with GHC 6.6, and I'm quite happy with it, but if there are other users of RPM-based distros out there, I'd appreciate it if you could kick the tyres a bit. Once it's in solid shape, I hope to plug this capability into Hackage so that there will automatically be fresh RPM packages available for Linux distributions such as Fedora. See the brief writeup here: http://www.serpentine.com/blog/2007/02/20/haskell-cabal-now-with-extra-crun… Cheers, <b

1 0

Haskell School of Expression
by Andrew Wagner 20 Feb '07

20 Feb '07

Has anyone worked through HSOE lately? I'm wondering if I'm going to be able to work through the examples that use their graphic library, under gtk2hs on fedora. Is there a workaround for this?

2 1