Re: [Haskell-cafe] Newbie: generating a truth table
On 2/10/07, Peter Berry [EMAIL PROTECTED] wrote: Prelude putStrLn $ concatMap (flip (++)\n) $ map show $ [(x,y,() x y) |x - [True,False],y - [True,False]] This can be simplified slightly to: Prelude putStrLn . unlines . map show $ [(x, y, x y) | x - [True, False], y - [True, False]] - Joe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell vs Ruby as a scripting language
Hi Simon Benchmarks please! Let's see some comparisons on the nofib suite. If there's a factor of 2 or less between GHC -O2 and YHC for any of the nofib programs, I'll eat my keyboard for lunch :-) http://www.cse.unsw.edu.au/~dons/nobench/bench.results Test: pidigits (lazy, arbitrary precision integers) http://www.cse.unsw.edu.au/~dons/code/nobench/imaginary/pidigits ghc 3.200seconds(1.0 x) ghci 3.500seconds(1.1 x) ghc-old 3.600seconds(1.1 x) yhc 5.740seconds(1.8 x) Would you like ketchup with that? ;) Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementation of scaled integers
On Tue, 13 Feb 2007, Stefan Heinzmann wrote: 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? I have implemented them in a generic way for NumericPrelude type classes: http://darcs.haskell.org/numericprelude/src/Number/FixedPoint.hs So far, I have only the interface http://darcs.haskell.org/numericprelude/src/Number/FixedPoint/Check.hs where the denominator is stored in the numbers and checked for each operation. But it would be easy to add another interface which retrieves the denominator from the type. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Data.Fixed and type encoded integers (Was: [Haskell-cafe] Implementation of scaled integers)
On Tue, 13 Feb 2007, Twan van Laarhoven wrote: Stefan Heinzmann wrote: 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? Data.Fixed [1] does exactly that, only it is based on Integer. Using fixed point with finite sized integers is more tricky, because you have to be careful not to get overflows in intermediate results. Is it a good idea to put the HasResolution type class and the types E6 and E12 in Data.Fixed? They are useful for every application where integers shall be encoded in types. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] exists . a psuedo-standard non-empty list module
On Thu, 15 Feb 2007, Nicolas Frisby wrote: I would also appreciate references to your favorite discussion about uses of head and other unsafe functions or various Oleg posts showing how they're all unnecessary. I'll find these on my own, but I would also like to know which ones strike a chord with the community. http://www.haskell.org/haskellwiki/Non-empty_list ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell vs Ruby as a scripting language
Neil Mitchell wrote: Hi Simon Benchmarks please! Let's see some comparisons on the nofib suite. If there's a factor of 2 or less between GHC -O2 and YHC for any of the nofib programs, I'll eat my keyboard for lunch :-) http://www.cse.unsw.edu.au/~dons/nobench/bench.results Test: pidigits (lazy, arbitrary precision integers) http://www.cse.unsw.edu.au/~dons/code/nobench/imaginary/pidigits ghc 3.200seconds(1.0 x) ghci 3.500seconds(1.1 x) ghc-old 3.600seconds(1.1 x) yhc 5.740seconds(1.8 x) Would you like ketchup with that? ;) pidigits is not (currently) one of the nofib programs (phew :-). I suppose the reason for the results is because the test spends most of its time in GMP? There are some other odd results in nobench, like the 2 programs where Hugs beats GHC that we need to look into. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell vs Ruby as a scripting language
simonmarhaskell: Neil Mitchell wrote: Hi Simon Benchmarks please! Let's see some comparisons on the nofib suite. If there's a factor of 2 or less between GHC -O2 and YHC for any of the nofib programs, I'll eat my keyboard for lunch :-) http://www.cse.unsw.edu.au/~dons/nobench/bench.results Test: pidigits (lazy, arbitrary precision integers) http://www.cse.unsw.edu.au/~dons/code/nobench/imaginary/pidigits ghc 3.200seconds(1.0 x) ghci 3.500seconds(1.1 x) ghc-old 3.600seconds(1.1 x) yhc 5.740seconds(1.8 x) Would you like ketchup with that? ;) pidigits is not (currently) one of the nofib programs (phew :-). I suppose the reason for the results is because the test spends most of its time in GMP? Right. If you look at the shootout, it really is a gmp bottleneck. There are some other odd results in nobench, like the 2 programs where Hugs beats GHC that we need to look into. Hugs only wins on one, atom, ghc hugs spectralatom3.520.55 this entry says in the src that hugs has historically beaten ghc here (by up to 20x in the past. From the src: It has the interesting property that Classic Hugs runs it 20x faster than GHC! Reason: runExperiment calls itself with identical parameters, and Hugs commons that up for some reason. (Even with that fixed, STG Hugs ran the program a lot slower than Classic Hugs.) So it seems like an interesting program. It appears here in the form with the silly self-call, because that makes it run a nice long time. It thrashes floating point multiplication and lists. The 'constraints' entry is also interesting, in that hbc is a fair bit faster there. The two where nhc98 wins are due to nhc98 producing the wrong output. The testsuite doesn't diff the output yet.. Another interesting one is clausify, which has a heap oflow in 6.6, but runs fine in 6.4.2. Generally things look pretty good. The Hbc (and possibly Hacle/Clean) results might indicate some areas to look at more closely. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Multiparameter class error
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Map list of functions over a single argument
On Tue, 20 Feb 2007 [EMAIL PROTECTED] wrote: Paul Moore wrote: I'm after a function, sort of equivalent to map, but rather than mapping a function over a list of arguments, I want to map a list of functions over the same argument. The signature would be [a - b] - a - [b], but hoogle didn't come up with anything. It seems like an obvious analogue of map, so I'm pretty sure I'm missing something (otherwise, I'd just write it myself, and not bother :-)) Can anyone point me in the right direction? It's also known as sequence :: Monad m = [m b] - m [b] with m = (-) a sequence :: [a - b] - (a - [b]) This is the fabulous MonadReader. Since there are a few questions, where 'sequence' is the answer - what about a 'sequence' honour Wiki page? I remember the combinatoric problem: http://www.haskell.org/pipermail/haskell-cafe/2006-June/015976.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Multiparameter class error
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] functional database queries
At http://www.haskell.org/hawiki/HaskellDbTutorial it is described, how database queries can be modelled with a monad. However, I wonder if this is also possible without monads. Say, writing DB.map col1 $ DB.filter (\row - col2 row == 10+2) myTable for SELECT col1 FROM MyTable where col2 = 10+2 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Multiparameter class error
Thanks, the functional dependency solved the problem
On 2/21/07, Yitzchak Gale [EMAIL PROTECTED] 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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Map list of functions over a single argument
On 2/21/07, Henning Thielemann [EMAIL PROTECTED] wrote: On Tue, 20 Feb 2007 [EMAIL PROTECTED] wrote: Paul Moore wrote: I'm after a function, sort of equivalent to map, but rather than mapping a function over a list of arguments, I want to map a list of functions over the same argument. Well this is not very sexy, no monads or anything, but I kinda believe in Keep It Simple: Prelude let revApply a f = f a Prelude let rMap a fs = map (revApply a) fs Prelude rMap 2 [(*4),(^2),(+12),(**0.5)] [8.0,4.0,14.0,1.4142135623730951] oh and I REALLY enjoyed the discussions that this spawned about things monadic, as there was some really slick stuff in there... The little thing about 'join' and etcetera... really good stuff. cheers... gene ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Map list of functions over a single argument
Gene A wrote: Well this is not very sexy, no monads or anything, but I kinda believe in Keep It Simple: Prelude let revApply a f = f a Prelude let rMap a fs = map (revApply a) fs Prelude rMap 2 [(*4),(^2),(+12),(**0.5)] [8.0,4.0,14.0,1.4142135623730951] Note that revApply here is precisely flip ($). And ($a) is the same as flip ($) a. So this reduces to one of the earlier examples rather quickly. It is possible to argue 'it's nice to give revApply a name'. It's also possible to argue 'taking a section of $ is even better than naming revApply'. Beauty in the eye of the beholder... Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type-level lambdas in Haskell? ( was Multiparameter class error)
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 fit 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 [EMAIL PROTECTED] wrote:
Thanks, the functional dependency solved the problem
On 2/21/07, Yitzchak Gale [EMAIL PROTECTED] 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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Saving the AST generated by Template Haskell
The example wasn't really clear, I anyway solved the issue. Here is a summary. The problem: There are some cases (at least when developing a DSEL with Templpate Haskell like I am) in which it might be really useful to keep the AST gathered by the TH quasi quotes for later processing during execution (not just at compile time as it is normally done). The solution: In order to do that it is necessary to splice the MetaAST (A TH AST expressed in TH AST syntax as well) of the AST which wants to be kept at compilation time. That MetaAST can be obtained by merely coding a Lift instance for Language.Haskell.TH.(Exp,Dec,Type), most of it is barely boilerplate code. In my opinion it would be a good idea to include an Lift instantiation of Language.Haskell.TH.(Exp,Dec,Type) in the TH library. On 1/25/07, Alfonso Acosta [EMAIL PROTECTED] wrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] functional database queries
Henning Thielemann wrote: At http://www.haskell.org/hawiki/HaskellDbTutorial it is described, how database queries can be modelled with a monad. However, I wonder if this is also possible without monads. Say, writing DB.map col1 $ DB.filter (\row - col2 row == 10+2) myTable for SELECT col1 FROM MyTable where col2 = 10+2 If and only if the database is a purely functional immutable data structure, this can be done. This is because the $ operator, function application, is used for control and/or dataflow. Many interesting databases are not purely functional immutable; most reside in the external world and can spontaneously change behind your program's back. The = operator generalizes from function application to these cases. Thus the monadic way subsumes the functional way and covers other uses. You can also make it an arrow. You can also make it an applicative. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] exists . a psuedo-standard non-empty list module
Hi Nick, On 2/16/07, Nicolas Frisby [EMAIL PROTECTED] wrote: I don't particularly like using fromJust or head, and there's been IMHO I think that isJust/fromJust could simply be removed. Using 'maybe' is a much better practice, it is safe and much even more expressive. head on the other hand might be considered more necessary but right now I cannot think of a situation in which it's use shows any advantage over simple pattern matching. It's anyway worth to check Neil's Safe library http://www-users.cs.york.ac.uk/~ndm/projects/safe/Safe.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: functional database queries
Henning Thielemann wrote: At http://www.haskell.org/hawiki/HaskellDbTutorial it is described, how database queries can be modelled with a monad. However, I wonder if this is also possible without monads. Say, writing DB.map col1 $ DB.filter (\row - col2 row == 10+2) myTable for SELECT col1 FROM MyTable where col2 = 10+2 Judging from the papers mentioned in the Haddocks, the monad is used like a list comprehension. This way, joins can be expressed as query = do x - table languages y - table programmers restrict (language ! paradigm .==. constant PurelyFunctional) ... Seems to be the main reason for a monadic interface. Of course, the query is compiled to SQL, so filter or its monadic equivalent cannot use arbitrary functions. This is prevented by giving x and y opaque types so that the programmer cannot really access them. I think this is why the monad feels a bit ill, i.e. despite the monad, subsequent actions cannot depend on the contents of x and y (because this contents is just a dummy). Albert Y. C. Lai wrote: If and only if the database is a purely functional immutable data structure, this can be done. [...] Many interesting databases are not purely functional immutable; most reside in the external world and can spontaneously change behind your program's back. I don't think this is the problem because SQL requests are emitted atomically anyway. The (Query a) monad here has nothing to do with mutability of the data base. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: functional database queries
[EMAIL PROTECTED] wrote: Albert Y. C. Lai wrote: If and only if the database is a purely functional immutable data structure, this can be done. [...] Many interesting databases are not purely functional immutable; most reside in the external world and can spontaneously change behind your program's back. I don't think this is the problem because SQL requests are emitted atomically anyway. The (Query a) monad here has nothing to do with mutability of the data base. The same clock read twice, each reading atomic, can give two different results. (Cf. the monadic type signature of Data.Time.Clock.getCurrentTime.) The same SELECT to the same database issued twice, each time atomic, can give two different results. These are not referentially transparent. These are not purely functional. The notation is a beauty bonus. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Leaves of a Tree
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Leaves of a Tree
Alternatively, the definition of your tree could include a list of linked
lists, one for each level of the tree. Then you could just select the last
list and it's the same as saving only the leaves from a complete inorder walk
of the tree.
data AltTree a = AltTree { tree_structure :: Tree a, nodes :: [[a]] }
On Wednesday 21 February 2007 14:31, Tom Hawkins wrote:
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: functional database queries
Albert Y. C. Lai wrote: [EMAIL PROTECTED] wrote: Albert Y. C. Lai wrote: If and only if the database is a purely functional immutable data structure, this can be done. [...] Many interesting databases are not purely functional immutable; most reside in the external world and can spontaneously change behind your program's back. I don't think this is the problem because SQL requests are emitted atomically anyway. The (Query a) monad here has nothing to do with mutability of the data base. The same clock read twice, each reading atomic, can give two different results. (Cf. the monadic type signature of Data.Time.Clock.getCurrentTime.) The same SELECT to the same database issued twice, each time atomic, can give two different results. Yeah, of course. That's why the function that executes the query is in the IO-monad: query :: GetRec er vr = Database - Query (Rel er) - IO [Record vr] Hennings' question is whether the query type 'Query (Rel el)' really has to be a monad, not whether the function 'query' has to be in the IO-monad. In other words, 'Query a' just assembles a valid SQL-string, it does not query or execute anything. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Map list of functions over a single argument
On 2/21/07, Jules Bean [EMAIL PROTECTED] wrote:
Gene A wrote:
Prelude let revApply a f = f a
Prelude let rMap a fs = map (revApply a) fs
Prelude rMap 2 [(*4),(^2),(+12),(**0.5)]
[8.0,4.0,14.0,1.4142135623730951]
Note that revApply here is precisely flip ($).
And ($a) is the same as flip ($) a.
So this reduces to one of the earlier examples rather quickly.
It is possible to argue 'it's nice to give revApply a name'. It's also
possible to argue 'taking a section of $ is even better than naming
revApply'.
-
jules,
.. right on... ran this through ghci...
let rMap a fs = map ($ a) fs
{ that is clean ... gotta admit.. }
Prelude rMap 2 [(*4),(^2),(+12),(**0.5)]
[8.0,4.0,14.0,1.4142135623730951]
Prelude :t rMap
rMap :: forall a b. a - [a - b] - [b]
About naming the secondary revApply function would agree and that would have
been in a where clause inside the definition of rMap had that been saved
to a file, but ghci doesn't really lend itself to multiline definitions so
that is why that was there, and it was also named in this case to show what
was going on... The functions as I originally defined them are probably
easier for someone new to Haskell to understand what was going on than the
rather stark ($ a) in the final factoring of the function... Though the
final resulting function is far the cleaner for that notation!
gene
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: generating a truth table
One possible way to generate the values would be using a generic function for permutation with repetition, such as: permuteRep :: [a] - [b] - [[(a,b)]] permuteRep [] _ = [] permuteRep (a:[]) bs = [ [ (a,b) ] | b - bs ] permuteRep (a:as) bs = concat [ [ (a,b):p | p - permuteRep as bs ] | b - bs ] and then use: lines = permuteRep [x,y,z] [False,True] In case the variable names can be discarded (or, in this case, not generated ... lazy evaluation rox ;-), then: map (map snd) lines This avoids having to provide a domain for each variable in the list comprehension, which could be problematic when dealing with many variables On 2/21/07, Joe Thornber [EMAIL PROTECTED] wrote: On 2/10/07, Peter Berry [EMAIL PROTECTED] wrote: Prelude putStrLn $ concatMap (flip (++)\n) $ map show $ [(x,y,() x y) |x - [True,False],y - [True,False]] This can be simplified slightly to: Prelude putStrLn . unlines . map show $ [(x, y, x y) | x - [True, False], y - [True, False]] - Joe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ricardo Guimarães Herrmann Those who do not understand Lisp are doomed to reinvent it, poorly Curried food and curried functions are both acquired tastes If you think good architecture is expensive, try bad architecture ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]
I would be interested in seeing a multithreaded solution, with each child thread crossing off the multiples of its own prime. The parent thread would be blocked from spawning a new thread for multiples of the next prime p until all existing child threads are past p. It is not clear to me what functional data structure would most efficiently accommodate this algorithm, however. Any suggestions? Dan Weston [EMAIL PROTECTED] wrote: Jens Blanck wrote: The point about Eratosthenes's sieve is that it does not specify algorithmically how to find the next number to be crossed. It does not even define how to store (crossed) numbers, it stores them on paper. But , I believe that Eratosthenes's sieve does specify how to store numbers and how to find the next to cross out. This is how I remember it: 0 List the numbers from 2 onwards. 1 Take first uncrossed number, say p. 2 Cross every pth number from there on (crossed or not). 3 Repeat from 1. And where's the storage specification? :) What I'd like to say is that in step 0, list the numbers may mean many things to the computer. For example, it can list them in a plain list or a finite map or a priority queue (or an array for the imperative). Yitzchaks 'deleteOrd' sieve uses a plain list whereas Melissa stores the crossed numbers in a priority queue. The choice has impact on how fast you can find the next number to be crossed: Yitzchak needs linear time whereas Melissa can do in logarithmic time. Here, time is parametrized by the count of primes smaller than the current number considered. In the end, the computer needs a more detailed description than the human who can see and cross numbers on a piece of paper at his choice. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: generating a truth table
On 2007-02-21, Joe Thornber [EMAIL PROTECTED] wrote: On 2007-02-10, Peter Berry [EMAIL PROTECTED] wrote: Prelude putStrLn $ concatMap (flip (++)\n) $ map show $ [(x,y,() x y) |x - [True,False],y - [True,False]] This can be simplified slightly to: Prelude putStrLn . unlines . map show $ [(x, y, x y) | x - [True, False], y - [True, False]] This can be further simplified to: putStrLn $ unlines [show (x, y, x y) | x - [True, False], y - [True, False]] -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ -- Using Opera's revolutionary e-mail client: https://secure.bmtmicro.com/opera/buy-opera.html?AID=789433 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Leaves of a Tree
tomahawkins: 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. Also, just check the strictness on the traversal function. A slightly different tree here might give some hints, http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytreeslang=ghcid=3 -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Leaves of a Tree
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] exists . a psuedo-standard non-empty list module
Hi IMHO I think that isJust/fromJust could simply be removed. Using 'maybe' is a much better practice, it is safe and much even more expressive. Yes, its more expressive if you let someone write (error Umm, what should I do here?) as one of the options. And now you've gone from something with a clear precondition, to something that merely floats a lazy _|_ value around the place. If you take that route be careful with strictness annotations! head on the other hand might be considered more necessary but right now I cannot think of a situation in which it's use shows any advantage over simple pattern matching. You can map head over a list, a function is a first class citizen. To make a pattern match into a first class item you need to turn it into a case or a lambda. Either way you can't import/export pattern matches from modules etc. I like both fromJust and head, they have clearly defined meanings, although obviously you have to be slightly careful about their use. Fortunately the problem of pattern match errors is being tackled by at least two projects: * Catch: http://www-users.cs.york.ac.uk/~ndm/projects/catch.php * ESC-Haskell: http://www.cl.cam.ac.uk/~nx200/research/escH-hw.ps Neither has a practical released tool yet, but hopefully that will have changed in a few months! It's anyway worth to check Neil's Safe library http://www-users.cs.york.ac.uk/~ndm/projects/safe/Safe.html Despite the fact that I like head/fromJust etc, a safe list library would be kind of handy. If someone wants to roll that into the Safe library, as Safe.List or something, I'd be happy to accept patches (saving someone else the hassle of setting up a new library etc, for roughly the same purpose) Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Leaves of a Tree
Hi Tom data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) leaves :: Tree - Set Int leaves (Leaf n) = singleton n leaves (Branch left right) = union (leaves left) (leaves right) The standard method for a traversal over leaves with accumulation is: leaves :: Tree - Set Int leaves x = f [] where f (Leaf n) rest = n : rest f (Branch l r) rest = f l (f r rest) This makes the construction of the list quite cheap. Then you can do the fromList trick, and that might give you a speed up. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: functional database queries
On Feb 21, 2007, at 20:47 , [EMAIL PROTECTED] wrote: Albert Y. C. Lai wrote: [EMAIL PROTECTED] wrote: Albert Y. C. Lai wrote: If and only if the database is a purely functional immutable data structure, this can be done. [...] Many interesting databases are not purely functional immutable; most reside in the external world and can spontaneously change behind your program's back. I don't think this is the problem because SQL requests are emitted atomically anyway. The (Query a) monad here has nothing to do with mutability of the data base. The same clock read twice, each reading atomic, can give two different results. (Cf. the monadic type signature of Data.Time.Clock.getCurrentTime.) The same SELECT to the same database issued twice, each time atomic, can give two different results. Yeah, of course. That's why the function that executes the query is in the IO-monad: query :: GetRec er vr = Database - Query (Rel er) - IO [Record vr] Hennings' question is whether the query type 'Query (Rel el)' really has to be a monad, not whether the function 'query' has to be in the IO-monad. In other words, 'Query a' just assembles a valid SQL-string, it does not query or execute anything. Regards, apfelmus This is correct, the Query monad is just used to construct the query. Running the query is done in IO. If we look in the source code (http://darcs.haskell.org/haskelldb/src/ Database/HaskellDB/Query.hs), we see that the Query monad is a state monad, whose state is the current query and an Int used to generate fresh field names. It would certainly possible to do this without a monad, though it would probably require reworking the PrimQuery type. /Björn___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Saving the AST generated by Template Haskell
Hi Ian, On 2/22/07, Ian Lynagh [EMAIL PROTECTED] wrote: I've just added th-lift to hackage (http://hackage.haskell.org/). You can use it to Derive lift for existing types. If only I knew about it before coding it by hand. It anyway it wasn't that bad cause I only support a subset of the AST and my hand-made Lift instance serves as well to cut detect unused branches. I wonder if there is any work being done to port DriFT to TH. It would be great, cause it wouldn't require using an external tool anymore and the affected Haskell code wouldn't need to be preprocessed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FFI basics
On 2/19/07, Yitzchak Gale [EMAIL PROTECTED] wrote: Simon Peyton-Jones wrote: Yitz, Please do make time to do this! This is the moment, while it is still fresh in your mind. Of course, you are correct. Thanks for the push. I am a bit busy with work, but the information is not lost. I'll have it up soon. I just did the same thing (started using FFI) and I had some questions, so I thought I would put up a slightly flawed wiki page and let people answer my questions by fixing the problems! The page is FFI Introduction, and the question is how to nicely integrate make to compile the C files and ghc --make for the haskell ones. Oops, I just realized I didn't use the recommended Using_the_FFI (it didn't show up on the wiki search, but I'm new to mediawiki...)! Oh well, it can be merged if necessary. Using seems to concentrate on calling haskell from C, mine is about calling C from haskell, and is more basic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] exists . a psuedo-standard non-empty list module
Despite the fact that I like head/fromJust etc, a safe list library would be kind of handy. If someone wants to roll that into the Safe library, as Safe.List or something, I'd be happy to accept patches (saving someone else the hassle of setting up a new library etc, for roughly the same purpose) Thanks Neil That sounds like a great option. Candidate numero uno as of now. What I have in mind right now should be pretty light weight, but it will mostly be a regurgitation of code I've seen floating around. Some of the code from the previous wiki link, type-level decimal numbers I saw in an Oleg paper (I think), etc. Would you be open to such code in your library? Anyone have a better place for it? Nick ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type-level lambdas in Haskell? ( was Multiparameter class error)
On 2/21/07, Alfonso Acosta [EMAIL PROTECTED] wrote: In my opinion adding Type-level lambdas would be the way to go, but they unfortunately are not part of Haskell. [snip] Is there any extension to the language covering type-level lambdas or even a plan to include them in next revision? SPJ suggested that type lambdas aren't in GHC because they unification for type inference impossible: http://www.mail-archive.com/haskell@haskell.org/msg10623.html The feature list for EHC indicates that it does support type lambdas, though I haven't tested this: http://www.cs.uu.nl/wiki/Ehc/LanguageFeatures A History of Haskell: http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm points to A system of constructor classes http://web.cecs.pdx.edu/~mpj/pubs/fpca93.html or http://citeseer.ist.psu.edu/jones95system.html regarding unification and type lambdas. Jim ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type-level lambdas in Haskell?
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Leaves of a Tree
On 2/21/07, Chad Scherrer [EMAIL PROTECTED] wrote: 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? Folding was my first approach: leaves :: Tree - Set Int leaves tree = accumLeaves Set.empty tree accumLeaves :: Set Int - Tree - Set Int accumLeaves set (Leaf n) = insert n set accumLeaves set (Branch l r) = foldl accumLeaves set [l,r] However, with this approach I quickly ran out of stack space. I found this odd, since I thought this program was tail recursive and shouldn't be using the stack. My next attempt was to use some form of memorization. Since many of the branches in my trees are equal, memorization should prevent following branches that have already been calculated. My question is, what is the best way to transform the original function to incorporate memorization? -Tom 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Leaves of a Tree
Neil, I think this idea is better than what I had suggested, but as it stands it doesn't typecheck. Did you mean something like this? leaves :: Tree - [Int] leaves = f [] where f rest (Leaf n) = n : rest f rest (Branch l r) = f (f rest r) l -Chad --- (from Neil Mitchell) Hi Tom data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) leaves :: Tree - Set Int leaves (Leaf n) = singleton n leaves (Branch left right) = union (leaves left) (leaves right) The standard method for a traversal over leaves with accumulation is: leaves :: Tree - Set Int leaves x = f [] where f (Leaf n) rest = n : rest f (Branch l r) rest = f l (f r rest) This makes the construction of the list quite cheap. Then you can do the fromList trick, and that might give you a speed up. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A real Haskell Cookbook
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is anyone using CUDA with haskell yet?
I don't want to duplicate anyone's work, and I'm not sure that NDA would allow me to release the code in any case (have to check on it carefully), but is anyone currently using the CUDA framework from nVidia inside of Haskell for highly parallel programming? -- Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A real Haskell Cookbook
I second this plea. -- Jeff On Wednesday 21 February 2007 22:34, P. R. Stanley 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type-level lambdas in Haskell? ( was Multiparameter class error)
Alfonso Acosta wrote:
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 - HDSignal 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
First of all, the design already exhibits the problem:
delaySY :: HDPrimType a = a - HDSignal a - HDSignal a
cannot be made _at all_ the member of an instantiated Synchronous
class. The reason is that in the class definition
class Synchronous s f1 f2 | s - f1, s - f2 where
delaySY:: a - s a - s a
the function delaySY is declared *fully* polymorphic over 'a' -- there
are no constraints on a and no restrictions. However,
delaySY :: HDPrimType a = a - HDSignal a - HDSignal a
shows that 'a' is constrained to satisfy the HDPrimType a.
That's the problem: the latter function is not generic enough.
The problem is described (and solved) in a message `Restricted
Datatypes Now'
http://www.haskell.org/pipermail/haskell-prime/2006-February/000498.html
I'm not certain if there is a compelling reason to place mapSY,
delaySY and zipWithSY in the same class. If not, the following is the
solution to the problem. Both sets of mapSY, delaySY and zipWithSY are
unified in overloaded functions:
{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-}
module SY where
class SynchronousM arg1 s a b | s a b - arg1 where
mapSY :: arg1 - s a - s b
class SynchronousD s a where
delaySY:: a - s a - s a
class SynchronousZ arg1 s a b c | s a b c - arg1 where
zipWithSY :: arg1 - s a - s b - s c
-- stubs
newtype Signal a = Signal a
newtype HDSignal a = HDSignal a
newtype HDFun a = HDFun a
class HDPrimType a where
cnv :: a - a; cnv = id
instance HDPrimType Int
instance HDPrimType Bool
-- (not so) Grand Unification
instance SynchronousM (a-b) Signal a b where
mapSY f (Signal x) = Signal (f x)
instance (HDPrimType a, HDPrimType b)
= SynchronousM (HDFun (a-b)) HDSignal a b where
mapSY (HDFun f) (HDSignal x) = HDSignal (cnv . f . cnv $ x)
instance SynchronousD Signal a where
delaySY _ = id
instance HDPrimType a = SynchronousD HDSignal a where
delaySY _ (HDSignal x) = HDSignal (cnv x)
instance SynchronousZ (a-b-c) Signal a b c where
zipWithSY f (Signal x) (Signal y) = Signal (f x y)
instance (HDPrimType a, HDPrimType b, HDPrimType c) =
SynchronousZ (HDFun (a-b-c)) HDSignal a b c where
zipWithSY (HDFun f) (HDSignal x) (HDSignal y) =
HDSignal (cnv (f (cnv x) (cnv y)))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type-level lambdas in Haskell? ( was Multiparameter class error)
On 2/22/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: First of all, the design already exhibits the problem: [snip] The reason is that [..] the function delaySY is declared *fully* polymorphic over 'a' -- there are no constraints on a and no restrictions. However, delaySY :: HDPrimType a = a - HDSignal a - HDSignal a I didn't even notice this problem. I'm not certain if there is a compelling reason to place mapSY, delaySY and zipWithSY in the same class There's not such a reason, I was just stupid enough to overlook that splitting the class would do the trick. If not, the following is the solution to the problem. Certainly :) Even if your solution doesn't look really elegant, it's the perfect workaround ... as it's the only one I have. Thanks a lot. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] TFP 2007: Registration and Program
Dear Colleagues, You may now resgister for TFP 2007! TFP 2007 will be held April 2-4, 2007 in New York City, USA. Our invited speaker is John McCarthy, Stanford University. Further details can be found at our homepage: http://cs.shu.edu/tfp2007/ . You may register at: http://cs.shu.edu/tfp2007/registration.html . The registration deadline is March 2, 2007 (11:59 p.m. EST). Accomodations information may be found at: http://cs.shu.edu/tfp2007/accomodations.html . We kindly remind you that the deadline to make a hotel reservation at the guaranteed rates offered to TFP 2007 participants is also quickly approaching. We are proud to announce our program of accepted talks: Unifying Hybrid Types and Contracts Jessica Gronski and Cormac Flanagan A Dual Semantics for the Data Description Calculus Yitzhak Mandelbaum, Kathleen Fisher, and David Walker A Metalanguage for Structural Operational Semantics Matthew Lakin and Andrew Pitts An Arrow Based Semantics for Interactive Applications Peter Achten, Marko van Eekelen, Maarten de Mol, and Rinus Plasmeijer Dependent Types: Easy as Pie Dimitrios Vytiniotis and Stephanie Weirich Constructing Correct Circuits -- Hardware Modelling with Dependent Types Edwin Brady, James McKinna, and Kevin Hammond Why Would Extensible Dependent Types Matter Pablo Nogueira and Bruno Oliveira Bytecode Verification for Haskell Robert Dockins and Samuel Z. Guyer UnreadTVar: Extending Haskell Software Transactional Memory for Performance Nehir Sonmez, Cristian Perfumo, Srdjan Stipic, Adrian Cristal, Osman S. Unsal, and Mateo Valero A New Functional Implementation of Grover's Fast Search Algorithm Justin Stallard and Murray Gross An Inference Algorithm for Guaranteeing Safe Destruction Manuel Montenegro, Ricardo Peña, and Clara Segura Hierarchical Master/Worker Skeletons Jost Berthold, Mischa Dieterle, Rita Loogen, and Steffen Priebe Property Directed Generation of First-Order Test Data Fredrik Lindblad Refactoring for Comprehension Gustavo Villavicencio Towards a Box Calculus for Hume Gudmund Grov and Greg Michaelson Scaled Regression: A Refinement of Primitive Recursion Daniel Leivant Equality-Based Uniqueness Typing Edsko de Vries, Rinus Plasmeijer, and David Abrahamson Lightweight Static Resources: Sexy Types for Embedded and Systems Programming Oleg Kiselyov and Chung-chieh Shan Space-Efficient Gradual Typing David Herman, Aaron Tomb, and Cormac Flanagan Use-Based Reference of Polymorphism Dave King and John Hannan Designing a Generic Graph Library Using ML Functors Sylvain Conchon, Jean-Christophe Filliatre, and Julien Signoles The SCIence Joint Research Activity Kevin Hammond, Dana Petcu, Phil Trinder, Abdallah Al Zain, Steve Linton, and Greg Michaelson Generic and Index Programming Jeremy Gibbons, Meng Wang, and Bruno C d. S. Oliveira The AHA Project Marko van Eekelen, Olha Shkaravska, Ron van Kesteren, Bart Jacobs, Sjaak Smetsers, and Erik Poll Studying Helium Program Bahaviour with the Neon Library Jurriaan Hage and Peter van Keeken Design and Implementation of JFP Hao Xu Hop Client-Side Compilation Florian Loitsch Adaptive High-Level Scheduling in a Generic Parallel Runtime Environment Jost Berthold, Abyd Al-Zain, and Hans-Wolfgang Loidl Bundles Pack Tighter than Lists Francisco Lopez-Fraguas, Juan Rodriguez-Hortala, and Jaime Sanchez-Hernandez Model-Based Testing of Thin-Client Web Applications and Navigation Input Pieter Koopman, Peter Achten, and Rinus Plasmeijer We look forward to seeing you at TFP 2007! Cheers, Marco Dr. Marco T. Morazan TFP 2007 Program Committee Chair http://cs.shu.edu/tfp2007/___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Leaves of a Tree
Hi Tom, Tom Hawkins wrote: Folding was my first approach: leaves :: Tree - Set Int leaves tree = accumLeaves Set.empty tree accumLeaves :: Set Int - Tree - Set Int accumLeaves set (Leaf n) = insert n set accumLeaves set (Branch l r) = foldl accumLeaves set [l,r] However, with this approach I quickly ran out of stack space. I found this odd, since I thought this program was tail recursive and shouldn't be using the stack. This is a problem of tail recursion and lazy evaluation not playing nicely. See this page: http://www.haskell.org/haskellwiki/Stack_overflow My next attempt was to use some form of memorization. Since many of the branches in my trees are equal, memorization should prevent following branches that have already been calculated. My question is, what is the best way to transform the original function to incorporate memorization? I think something like this could be done, if there's some invariants maintained by the data structure. Is there any additional structure you're imposing beyond that required for the data line? -Chad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
