Re: [Haskell-cafe] New slogan for haskell.org
On Wed, 12 Dec 2007, Bill Wood wrote: On Wed, 2007-12-12 at 11:19 +, Andrew Coppin wrote: . . . ...and normal programmers care about the Fibonacci numbers because...? Seriously, there are many, many programmers who don't even know what Fibonacci numbers *are*. And even I can't think of a useful purpose for them. (Unless you count Fibonacci codes?) Knuth[1] pp. 417-419 discusses Fibonacci trees and Fibonacci search. According to Knuth (and who am I to argue with him) Fibonacci search has better average case running time than binary search, although worst case can be slightly slower. Cormen et. al.[2] devotes chapter 20 to Fibonacci heaps, which they say are of primarily theoretical interest. [1] Donald E. Knuth, The Art of Computer Programming, vol. 3, second edition, Addison Wesley Longman (1998). [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, second edition, The MIT Press (2001). Worst case analysis of AVL trees also leads to Fibonacci numbers, as far as I remember. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
On Fri, 14 Dec 2007, Henning Thielemann wrote: Worst case analysis of AVL trees also leads to Fibonacci numbers, as far as I remember. The number of possibilities to arrange bricks of a certain width is also Fibonacci number. In general I think that Fibonacci numbers serve as simple non-trivial example for difference equations. | | || -- || -- ||| |-- --| ||| |-- --| ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Software Tools in Haskell
On Wed, 12 Dec 2007, Don Stewart wrote: ndmitchell: A much simpler version: main = print . length . words = getContents Beautiful, specification orientated, composed of abstract components. My thoughts too when reading the initial post was that it was all very low level imperative programming. Not of the Haskell flavour. I remember there was a discussion about how to implement full 'wc' in an elegant but maximally lazy form, that is counting bytes, words and lines in one go. Did someone have a nice idea of how to compose the three counters from implementations of each counter? I'm afraid one cannot simply use the split and count fragments trick then. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Execution of external command
Evan Laforge wrote: it seems that script may be not terminated if its output isn't read, so better code should be (_, h, g, _) - runInteractiveCommand script params result - hGetLine h hGetContents h = evaluate.length hGetContents g = evaluate.length Tangent here, but does anyone else think that something like hGetContentsEagerly would be handy in System.IO? YES! Jules PS we could give it a nice sensible name like hGetContents. We could renaming the existing hGetContents to hUnsafeGetContentsDontUseThisUnlessYouHaveSpentThreeMonthsLearningGHCsExecutionSemanticsOrYouWillRegretIt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Execution of external command
Hello Jules, Friday, December 14, 2007, 12:21:30 PM, you wrote: PS we could give it a nice sensible name like hGetContents. We could renaming the existing hGetContents to hUnsafeGetContentsDontUseThisUnlessYouHaveSpentThreeMonthsLearningGHCsExecutionSemanticsOrYouWillRegretIt i have more advanced proposal - we should include in its name whole paper on its semantics so anyone using it will be clearly warned. moreover, any suggestion to use this function will automatically include exact description of its caveats that is again The Right Thing To Do :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Examples of useful functions of order = 3?
Hi all, I'm working on a type-based side effect analysis for a Haskell-like language, and need to test it against some more higher order functions. The situation is a bit icky because it uses bounded quantification and various related issues (ie covariance vs contravariance) only come into play when dealing with functions of order = 3. Trouble is, the vast majority of useful higher order functions that I can think of are of order 2. Oh, I can certainly invent toys like: order3 f = f succ order4 b f = if b then f else order3 .. and so on, but I'm left feeling unsatisfied. I vaguely remember a paper called something like Is there any use for a seventh order function?, but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places. Does anyone have any examples of code (in whatever language) which usefully uses functions of order = 3?? Preferably up to 5? Thanks, Ben. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monads that are Comonads and the role of Adjunction
Dan Weston wrote: apfelmus wrote: Luke Palmer wrote: Isn't a type which is both a Monad and a Comonad just Identity? (I'm actually not sure, I'm just conjecting) Good idea, but it's not the case. data L a = One a | Cons a (L a) -- non-empty list Maybe I can entice you to elaborate slightly. From http://www.eyrie.org/~zednenem/2004/hsce/Control.Functor.html and Control.Comonad.html there is -- newtype O f g a -- Functor composition: f `O` g instance (Functor f, Functor g) = Functor (O f g) where ... instance Adjunction f g = Monad (O g f) where ... instance Adjunction f g = Comonad (O f g) where ... -- I assume Haskell can infer Functor (O g f) from Monad (O g f), which -- is why that is missing here? No. But it can infer Functor (O g f) from instance (Functor f, Functor g) = Functor (O f g), (using 'g' for 'f' and 'f' for 'g'). class (Functor f, Functor g) = Adjunction f g | f - g, g - f where leftAdjunct :: (f a - b) - a - g b rightAdjunct :: (a - g b) - f a - b -- Functors are associative but not generally commutative. Apparently a Monad is also a Comonad if there exist left (f) and right (g) adjuncts that commute. [and only if also??? Is there a contrary example of a Monad/Comonad for which no such f and g exist?] In the case of data L a = One a | Cons a (L a) -- non-empty list what are the appropriate definitions of leftAdjunct and rightAdjunct? Are they Monad.return and Comonad.extract respectively? That seems to unify a and b unnecessarily. Do they wrap bind and cobind? Are they of any practical utility? I think you're asking the wrong question! The first question needs to be : What is f and what is g ? What are the two Functors in this case? We know that we want g `O` f to be L, because we know that the unit is return, i.e. One, and unit :: a - O g f a otherwise known as eta :: a - O g f a We also know there is a co-unit epsilon :: O f g a - a, but we don't know much about that until we work out how to decompose L into two Functors. There are two standard ways to decompose a monad into two adjoint functors: the Kleisli decomposition and the Eilenberg-Moore decomposition. However, neither of these categories is a subcategory of Hask in an obvious way, so I don't immediately see how to write f and g as haskell functors. Maybe someone else can show the way :) Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: -threaded
Maurício wrote: I see in the documentation and in many messages in this list that, if you want multithreading in your program, you need to use -threaded in ghc. Concurrency is supported just fine without -threaded. You need -threaded if you want to: 1) make foreign calls that do not block other threads 2) use multiple CPUs 3) write a multithreaded Haskell library or DLL Some library functions use foreign calls, for example System.Process.waitForProcess, so if you want to use them without blocking other threads you need -threaded. From an implementation perspective, -threaded enables OS-thread support in the runtime. Without -threaded, everything runs in a single OS thread. The features listed above all require multiple OS threads. Why isn't that option default? Does it imply some kind of overhead? There may be an overhead, because the runtime has to use synchronisation in various places. Hopefully the overhead is negligible for most things. It's not the default mostly for historical reasons, and because there are people who don't like to get multiple OS threads unless they ask for it. Also there are one or two things that don't work well with -threaded (Gtk2Hs, and System.Posix.forkProcess). Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle error
Hi Hi. Sorry, I should have put the question differently -- is there sometimes a need to escape hoogle input (i.e. so I could confirm there were no results, rather than getting an error)? The only one I'm aware of is that searching for any operator such as (+) needs to be done without brackets. But, thinking about it, there's no reason that this shouldn't give an error as it isn't a type sig. (I was looking for source online somewhere of the monad instance for (-) and only entered it in hoogle out of curiosity...) If any syntax did work for this, I'd have expected it to be something like instance Monad (-). Unfortunately that won't work, and I'm not sure I even can make it work in future versions, since Hoogle is unable to tell where an instance is defined - Haddock abstracts away this information. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: -threaded
Simon Marlow [EMAIL PROTECTED] writes: Concurrency is supported just fine without -threaded. You need -threaded if you want to: : 3) write a multithreaded Haskell library or DLL I thought -threaded (A.K.A. -smp, no?) only affected which runtime was used, and thus was a linking option. I do have a library that needs -smp, but as far as I knew, the onus would be on the *applications* to specify this when compiling/linking. Is that incorrect? Is there a way for a library to inform the application about this? -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Examples of useful functions of order = 3?
Ben Lippmeier wrote: I vaguely remember a paper called something like Is there any use for a seventh order function?, but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places. Does anyone have any examples of code (in whatever language) which usefully uses functions of order = 3?? Preferably up to 5? I don't know, but you can probably use church-encodings to pimp up the order: type Bool = ∀a . a - a - a -- order a + 1 type List a = ∀b . (a - b - b) - b - b -- max (order a, order b) + 1 not :: Bool - Bool -- order 2 map :: (a - a) - List a - List a -- order 3 + order a To avoid higher-rank polymorphism, just choose some arbitrary fixed types not':: (A - A - A) - (A - A - A) filter' :: (A - A) - ((A - B - B) - B - B) - ((A - B - B) - B - B) Those functions probably aren't that useful anymore, but they once were :) Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] type classes
I'd like to define several instances of the same type class with the same type variable instance. Only method instances differ. How can I do this without writing copies of the type class? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Problems with split-objs
On Dec 14, 2007 12:14 AM, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-11-26 at 22:48 +, Magnus Therning wrote: I've followed the instructions at [1] to create a .deb of vty[2]. It seems the helper scripts for Debian passes `--enable-split-obj' when running `./Setup.lhs configure'. This results in numerous multiple definitions of stuff. I have a few questions regarding this... I find this is usually due to a bad combination of ghc and gcc. eg ghc-6.6.x and gcc-4.2 have this problem on a couple arches. What versions of stuff are you using? That explains it then. I'm on Debian Sid, which means I currently have ghc 6.6.1 and gcc 4.2.3 (prerelease). Bugger! /M ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Generics: how do I get the type name of a value?
Hi http://haskell.org/hoogle/?q=typeOf C:\ghci GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude :m Data.Typeable Prelude Data.Typeable typeOf neil [Char] Another great thing is that this bit also works in Hugs, while the Data.Generics stuff is GHC only. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type classes
Peter Padawitz wrote:
I'd like to define several instances of the same type class with the
same type variable instance. Only method instances differ. How can I do
this without writing copies of the type class?
newtypes and modules have both been suggested.
I have another suggestion:
Don't!
Don't use typeclasses.
The only useful thing about typeclasses is that they are a kind of
type-indexed family of dictionaries. If you don't want to use the type
indexin, then don't use classes. Just use your own kind of dictionary.
E.g., instead of:
class Foo a where { bar :: a - Int; baz :: a - String }
instance Foo Double ...
instance Foo Double ... -- bother, I wanted a different Double instance!
you should just have:
data Foo a = Foo { bar :: a - Int, baz :: a - String }
foo1 :: Foo Double
foo1 = Foo { ... }
foo2 :: Foo Double
foo2 = Foo { ... }
-- now I can have as many 'instances' for the same type as I want!
Jules
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: -threaded
Ketil Malde wrote: Simon Marlow [EMAIL PROTECTED] writes: Concurrency is supported just fine without -threaded. You need -threaded if you want to: : 3) write a multithreaded Haskell library or DLL I thought -threaded (A.K.A. -smp, no?) only affected which runtime was used, and thus was a linking option. I do have a library that needs -smp, but as far as I knew, the onus would be on the *applications* to specify this when compiling/linking. Is that incorrect? Is there a way for a library to inform the application about this? Sorry, I was a bit ambiguous there: for case (3) I mean a Haskell library that you intend to call from C, or some other foreign language, using multiple OS threads. You're absolutely right that for a Haskell library that you intend to call from Haskell, the -threaded option is used when the final program is linked, there's no way for the library itself to add it. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Data.Generics: how do I get the type name of a value?
I've been learning/playing with Data.Generics a bit, and have a how-to
question...
If I say
dataTypeOf
then I get
DataType {tycon = Prelude.[], datarep = AlgRep [[],(:)]}
No surprises there. But I'd really like to know that I have a String,
or [Char]. How do I get the name of the concrete type that the list
contains? Is that a reasonable thing to ask for?
I can say:
gmapQ dataTypeOf a
to get:
[ DataType {tycon = Prelude.Char, datarep = StringRep}
, DataType {tycon = Prelude.[], datarep = AlgRep [[],(:)]}
]
But if I say:
gmapQ dataTypeOf
I get:
[]
which makes sense when you consider the stucture of the List ADT, but
doesn't help me determine the type of the value.
Alistair
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type classes
Lutz Donnerhacke [EMAIL PROTECTED] writes: * Peter Padawitz wrote: I'd like to define several instances of the same type class with the same type variable instance. Only method instances differ. How can I do this without writing copies of the type class? Define the type class in a module named MyClass. Define the each instance in a module named MyInstanceX where X is a version number. Include only the MyInstanceX module, you currently need. Or, if you need more than one at the same time, wrap your data type in one newtype per instance. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Generics: how do I get the type name of a value?
On 14/12/2007, Neil Mitchell [EMAIL PROTECTED] wrote: http://haskell.org/hoogle/?q=typeOf Another great thing is that this bit also works in Hugs, while the Data.Generics stuff is GHC only. Great, thanks. Didn't occur to me to look further up the class hierarchy :-) Alistair ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Generics: how do I get the type name of a value?
Hi Alistair,
http://haskell.org/hoogle/?q=typeOf
C:\ghci
GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
Prelude :m Data.Typeable
Prelude Data.Typeable typeOf neil
[Char]
Thanks
Neil
On 12/14/07, Alistair Bayley [EMAIL PROTECTED] wrote:
I've been learning/playing with Data.Generics a bit, and have a how-to
question...
If I say
dataTypeOf
then I get
DataType {tycon = Prelude.[], datarep = AlgRep [[],(:)]}
No surprises there. But I'd really like to know that I have a String,
or [Char]. How do I get the name of the concrete type that the list
contains? Is that a reasonable thing to ask for?
I can say:
gmapQ dataTypeOf a
to get:
[ DataType {tycon = Prelude.Char, datarep = StringRep}
, DataType {tycon = Prelude.[], datarep = AlgRep [[],(:)]}
]
But if I say:
gmapQ dataTypeOf
I get:
[]
which makes sense when you consider the stucture of the List ADT, but
doesn't help me determine the type of the value.
Alistair
___
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] type classes
* Peter Padawitz wrote: I'd like to define several instances of the same type class with the same type variable instance. Only method instances differ. How can I do this without writing copies of the type class? Define the type class in a module named MyClass. Define the each instance in a module named MyInstanceX where X is a version number. Include only the MyInstanceX module, you currently need. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GUI
I have just successfully built Gtk2Hs against the native Mac OS X port of Gtk at: http://developer.imendio.com/projects/gtk-macosx This implies we can now use Gtk2Hs on the Mac without X11. The sample apps still look rather alien compared to normal Mac apps, but they are a big improvement over the X11 version. Regards, Neil On 12 Dec 2007, at 19:40, Miguel Mitrofanov wrote: Is there any really cross-platform GUI library for Haskell? Gtk2Hs is good (I suppose), but it requires X. OK, I have X, but it's not native on my Mac; some Mac users don't install it and almost all Mac users don't always run it. I was able to install wxHaskell (after some hacking - this was really painful); and Blobs editor compiled successfully, but then resisted to run. Tk-based libraries seem to be good, and Tk can be run natively on Mac (i.e., without X), but none of them seem to compile. Sorry if this message seems like I'm angry; I am, but that's only for a moment. ___ 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] array documentation is missing
While trying to make Regex.TDFA 0.91 install on 6.8.2 I got [10 of 21] Compiling Text.Regex.TDFA.RunMutState ( Text/Regex/TDFA/RunMutState.\ hs, dist\build/Text/Regex/TDFA/RunMutState.o ) Text/Regex/TDFA/RunMutState.hs:601:9: Constructor `STUArray' should have 4 arguments, but has been given 3 In the pattern: STUArray _ _ msource In the definition of `copySTU': copySTU (STUArray _ _ msource) (STUArray _ _ mdest) = ST $ \ s1# - case sizeofMutableByteArray# msource of n# -\ ... ^[]0;~/hackageTarGzs/regexstuff/regex-tdfa-0.92^G [EMAIL PROTECTED] ^[[33m~/hackageTarGzs/regexstuff/regex-tdfa-0.92^[\ [0m but I got stuck fixing it because the array documentation isn't there http://www.haskell.org/ghc/docs/latest/html/libraries/haskell98/Array.html assume I'm getting the above error because the array interface has changed thomas. --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Strict String IO now packaged
Here at Haskell.org we know you have a choice in programming languages, and a choice in evaluation strategies. To help make your decision easier, I'm pleased to announce an update to the 'strict' package providing strict file IO for Strings. You can now choose when and where to evaluate your Strings, meaning more predictable resource usage for readFile-like Strict IO. And of course you can still use lazy IO when appropriate. Find the strict IO package in System.IO.Strict, on hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict Cheers, Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monads that are Comonads and the role of Adjunction
On Dec 14, 2007 5:14 AM, Jules Bean [EMAIL PROTECTED] wrote:
There are two standard ways to decompose a monad into two adjoint
functors: the Kleisli decomposition and the Eilenberg-Moore decomposition.
However, neither of these categories is a subcategory of Hask in an
obvious way, so I don't immediately see how to write f and g as
haskell functors.
Maybe someone else can show the way :)
One possibility is to extend Haskell's Functor class. We can define a class
of (some) categories whose objects are Haskell types:
class Category mor where
id :: mor a a
(.) :: mor b c - mor a b - mor a c
The instance for (-) should be obvious. We can also define an instance for
Kleisli operations:
newtype Kleisli m a b = Kleisli { runKleisli :: a - m b }
instance (Monad m) = Category (Kleisli m) -- omitted
Next, a class for (some) functors between these categories:
class (Category morS, Category morT) = Functor f morS morT where
fmap :: morS a b - morT (f a) (f b)
Unlike the usual Haskell Functor class, this requires us to distinguish the
functor itself from the type constructor involved in the functor.
Here's an instance converting Kleisli operations to functions.
instance Monad m = Functor m (Kleisli m) (-) where
-- fmap :: Kleisli m a b - (m a - m b)
fmap f = (= runKleisli f)
Going the other way is tricker, because our Functor interface requires a
type constructor. We'll use Id.
newtype Id a = Id { unId :: a }
instance Monad m = Functor Id (-) (Kleisli m) where
-- fmap :: (a - b) - Kleisli m (Id a) (Id b)
fmap f = Kleisli (return . Id . f . unId)
Finally, adjunctions between functors:
class (Functor f morS morT, Functor g morT morS)
= Adjunction f g morS morT | f g morS - morT, f g morT - morS
where
leftAdj :: morT (f a) b - morS a (g b)
rightAdj :: morS a (g b) - morT (f a) b
The functional dependency isn't really justified. It's there to eliminate
ambiguity in the later code.
The two functors above are adjoint:
instance (Monad m) = Adjunction Id m (-) (Kleisli m) where
-- leftAdj :: Kleisli (Id a) b - (a - m b)
leftAdj f = runKleisli f . Id
-- rightAdj :: (a - m b) - Kleisli (Id a) b
rightAdj f = Kleisli (f . unId)
So, given two adjoint functors, we have a monad and a comonad. Note,
however, that these aren't necessarily the same as the Haskell classes Monad
and Comonad.
Here are the monad operations:
unit :: (Adjunction f g morS morT) = morS a (g(f a))
unit = leftAdj id
extend :: (Adjunction f g morS morT) = morS a (g(f b)) - morS (g(f a))
(g(f b))
extend f = fmap (rightAdj f)
The monad's type constructor is the composition of g and f. Extend
corresponds to (=) with the arguments reversed.
In our running example, unit and extend have these types:
unit :: Monad m = a - m (Id a)
extend :: Monad m = (a - m (Id b)) - m (Id a) - m (Id b)
This corresponds to our original monad, only with the extra Id.
Here are the comonad operations:
counit :: (Adjunction f g morS morT) = morT (f(g a)) a
counit = rightAdj id
coextend :: (Adjunction f g morS morT) = morT (f(g a)) b - morT (f(g a))
(f(g b))
coextend f = fmap (leftAdj f)
In our running example, counit and coextend have these types:
counit :: Monad m = Kleisli m (Id (m a)) a
coextend :: Monad m = Kleisli m (Id (m a)) b - Kleisli m (Id (m a))
(Id (m b))
Thus, m is effectively a comonad in its Kleisli category.
We can tell a similar story with Comonads and CoKleisli operations,
eventually reaching an adjunction like this:
instance (Comonad w) = Adjunction w Id (CoKleisli w) (-) -- omitted
--
Dave Menendez [EMAIL PROTECTED]
http://www.eyrie.org/~zednenem/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Fw: hdbc odbc also crashes on 6.8.2 Re: [Haskell-cafe] HDBC-ODBC crashes on ghc 6.8
I just tried HDBC-ODBC on 6.8.2, but it still crashes. Works on 6.6.1. thomas. Thomas Hartman [EMAIL PROTECTED] Sent by: [EMAIL PROTECTED] 11/19/2007 12:05 PM To haskell-cafe@haskell.org cc Subject [Haskell-cafe] HDBC-ODBC crashes on ghc 6.8 This minimal program below fails in 6.8.1, works for 6.6.1, for up to date HDBC-ODBC-1.1.3. (I tried installing both from package and from darcs head) Installed and running from cygwin. When I run it as runghc fail.hs I get a windows popup error ghc.exe has encountered a problem and needs to close, sorry for the inconvenience. ghci, same behavior. When I run it as ghc -e 'main' fail.hs, I don't get a popup window, and no error message is output, but it fails all the same. (I know this because more complicated, non-minimal programs, fail.) So this would seem to be a problem with ghc 6.8.1. $ cat fail.hs import Database.HDBC import Database.HDBC.ODBC main = connectODBC some valid connect string, works when run from 6.6.1, not from 6.8.1 --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] array documentation is missing
On 14 Dec 2007, [EMAIL PROTECTED] wrote: but I got stuck fixing it because the array documentation isn't there http://www.haskell.org/ghc/docs/latest/html/libraries/haskell98/Array.html Try the hierarchical library docs: http://haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-MArray.html http://haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-ST.html Jed pgpjdAkVLycE4.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
I'm working through the interesting paper Data type à la carte and am confused by the Functor instance for Val. I think this stems from some confusion of mine regarding the Functor class in general. The Functor instance I'm confused about is: instance Functor Val where fmap f (Val x ) = Val x where Val is defined as: data Val e = Val Int Is this the only valid Functor instance for the Val type? Even though I'd, naively, expect the Functor instance to look like: instance Functor Val where fmap f (Val x) = Val (f x) I suspect that would not work out due to the type of the Val constructor. Is this correct? The reason I find all this odd is because I'm not sure how the type class Functor relates to the category theory concept of a functor. How does declaring a type constructor to be an instance of the Functor class relate to a functor? Is the type constructor considered a functor? Any help would be, of course, greatly appreciated. -Corey O'Connor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] JOB OFFER / Haskell for commercial projects?
Hello Happy Haskellers, I had to abandon improving my newbie Haskell skills the past weeks; I was busy creating a new startup company and finalizing financial funding for a cool project related to realtime 2D/3D animation and games. As I'm the CTO of this new company, and since I kinda like Haskell, I might consider creating a first prototype of the project using Haskell. However, this will be a commercial project. The software will be freely downloadable but not open source. However, if succesful, a highly priced professional version of the software might be created. Although I'm pretty sure GHC can be used for creating a private inhouse prototype, the prototype might evolve into the final product, and so my question is, which Haskell compilers tools can: (1) be used to build commercial projects (2) be shipped with commercial projects (our project might call into the interpreter/compiler at runtime.) (3) be indirectly used by commercial projects (in the sense that the user will have to manually download and install the compiler) Furthermore, is the Haskell community willing to provide the excellent help (as in this forum and on IIRC) for commercial Haskell projects? That said, anybody who might be interested in getting a (paid J) Haskell job (parttime or fulltime) in the field of computer animation and games (but also (visual) programming languages, interpreters compilers), please mailto:[EMAIL PROTECTED] Preferable you will work onsite (in Belgium / Antwerp - the city of diamonds J), although working remote is also an option. You will make software that will be initially used by computer artists (that among other things made parts of http://www.cgchannel.com/gallery/viewimage.jsp?imgID=547 The Girl, Xyanide http://www.gamespot.com/xbox/action/xyanide/index.html , and many commercials http://www.nazooka.com/site/html/index.php?p=movieplayerm=showreel ), that will be demonstrated at SIGGRAPH http://www.siggraph.org/ , and will be released to the public in a later stage. Cheers to all, Peter Verswyvelen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On Dec 14, 2007 11:44 AM, Corey O'Connor [EMAIL PROTECTED] wrote: I'm working through the interesting paper Data type à la carte and am confused by the Functor instance for Val. I think this stems from some confusion of mine regarding the Functor class in general. I'll try to explain, but I might not be very clear :). The Functor instance I'm confused about is: instance Functor Val where fmap f (Val x ) = Val x where Val is defined as: data Val e = Val Int Is this the only valid Functor instance for the Val type? Even though I'd, naively, expect the Functor instance to look like: instance Functor Val where fmap f (Val x) = Val (f x) Yes, I think people often expect this, because they're used to the idea that fmap applies a function to all the terminal elements in a data structure. For example, if you map a function across a list or tree, you expect the function to be applied to each value or node, not the branches themselves, and to preserve the structure of the tree or list. This is not the case when you use functors as you are in your email (I think sometimes called syntactic functors, for traversing abstract syntax trees); In this case, you are only pushing the function into all recursive subterms of a data structure, which the function then operates on. So, consider this data structure: data Val e = Add e e | Val Int instance Functor Val where fmap f (Val x) = Val x fmap f (Add x y) = Add (f x) (f y) Notice that it is not (fmap f x) and (fmap f y). You only push the function one level deeper, not all the way down (the catamorphism takes care of fmap-ing the function all the way down). I suspect that would not work out due to the type of the Val constructor. Is this correct? Correct, the types wouldn't work. Try it and see :) The reason I find all this odd is because I'm not sure how the type class Functor relates to the category theory concept of a functor. How does declaring a type constructor to be an instance of the Functor class relate to a functor? Is the type constructor considered a functor? I could try to answer this one, but I would just confuse both of us, heh. Hope I was helpful! Any help would be, of course, greatly appreciated. -Corey O'Connor ___ 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] #haskell works
Many people have written words to the effect that the #haskell IRC channel is just bursting with helpful Haskellers who are endlessly friendly and seemingly able to help solve any problem. Personally, this has never been my experience. (More like there's 300 people idling and nobody ever actually speaks...) I am pleased to report that last night I was on #haskell and I did in fact get lots of useful help, from a number of people. So first of all, thanks for that guys! It all relates to this simple program: http://hpaste.org/4438 I pointed out that you can write a complex explicit loop in Java, and that you can translate the same thing into Haskell, and it works. But in Haskell, you can also do it by composing a couple of functions, and it's much easier to read. Somebody else countered that while this is all very cute, it can never be efficient. To which I obviously countered that stream fusion *makes* it efficient. The numbers generated are thus: Program with no particular optimisations: 0.35 seconds. Program with stream fusion [and GHC HEAD]: 0.25 seconds. Program with stream fusion and ByteString: 0.05 seconds. Surely you'd have to work pretty hard to get that kind of speed even in C. ;-) ...erm, actually no. Somebody sat down and wrote something in five minutes that takes 0.005 seconds. Oops! So it seems even with ByteStrings and stream fusion, we're still 10x slower than naive C. :-( You can console yourself that maybe 5 milliseconds is too short a time span to reliably measure, and maybe the speed difference is just down to the OS caching the file in RAM or something. Maybe a benchmark of something that takes tens of seconds would be better. All I know is that once again, it seems Haskell isn't as fast as I thought... *sigh* Well anyway, a few years ago we didn't have fusion, and we didn't have ByteString. A few years ago, the program would have taken 0.35 seconds. The end. Today, with a few import statements and compiler switches, the exact same code takes 0.05 seconds. Tomorrow, who knows? Maybe I'm being overly optimistic, but... ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
Hi Corey, On Dec 14, 2007 8:44 PM, Corey O'Connor [EMAIL PROTECTED] wrote: The reason I find all this odd is because I'm not sure how the type class Functor relates to the category theory concept of a functor. How does declaring a type constructor to be an instance of the Functor class relate to a functor? Is the type constructor considered a functor? Recall the definition of functor. From Wikipedia: A functor F from C to D is a mapping that * associates to each object X in C an object F(X) in D, * associates to each morphism f:X - Y in C a morphism F(f):F(X) - F(Y) in D such that the following two properties hold: * F(idX) = idF(X) for every object X in C * F(g . f) = F(g) . F(f) for all morphisms f:X - Y and g:Y - Z. http://en.wikipedia.org/wiki/Functor We consider C = D = the category of types. Note that any type constructor is a mapping from types to types -- thus it associates to each object (type) X an object (type) F(X). Declaring a type constructor to be an instance of Functor means that you have to provide 'fmap :: (a - b) - (f a - f b) -- that is, a mapping that associates to each morphism (function) fn :: a - b a morphism fmap fn :: f a - f b. Making sure that the two laws are fulfilled is the responsibility of the programmer writing the instance of Functor. (I.e., you're not supposed to do this: instance Functor Val where fmap f (Val x) = Val (x+1).) Hope this helps with seeing the correspondence? :-) - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] #haskell works
On Dec 14, 2007 12:12 PM, Andrew Coppin [EMAIL PROTECTED] wrote: Today, with a few import statements and compiler switches, the exact same code takes 0.05 seconds. Tomorrow, who knows? Maybe I'm being overly optimistic, but... ;-) There have been some great improvements in array handling recently. I decided to have a look at the assembly language generated by some simple array manipulation code and understand why C is at least twice as fast as ghc 6.8.1. One the one hand it was disappointing to see that the Haskell register allocator seems a bit inept and was loading data into registers that should never have been spilled out of registers in the first place. On the other hand, the code wasn't fundamentally doing anything weird (eg. it wasn't doing graph reductions or anything like that, it looked like the sort of loop you might get from a C compiler). It was a few seconds of fairly mindless work to fix up the assembly language and make it much faster. And if I can do it, it means that the next generation of Haskell compiler should be able to do it too, after all, good freely available methods to allocate registers do exist. So I'm looking forward to the next version of GHC matching C's performance for inner loops of array manipulation code :-) -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On Dec 14, 2007 6:37 PM, Benja Fallenstein [EMAIL PROTECTED] wrote: such that the following two properties hold: * F(idX) = idF(X) for every object X in C * F(g . f) = F(g) . F(f) for all morphisms f:X - Y and g:Y - Z. Should we write instance Functor Val where fmap = undefined Would those properties be satisfied? Of course, fmap (g . f) == _|_ == fmap g . fmap f, but fmap id x == _|_ =/= x == id x. As my understanding of the relationship between bottoms and non-bottoms isn't that great, could anyone tell me if the above instance is sound (i.e. satisfy the expected properties)? If it is not, the implementation fmap f = id is really the only one sound, right? Thanks! -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] #haskell works
Hello Andrew, Friday, December 14, 2007, 11:12:18 PM, you wrote: So it seems even with ByteStrings and stream fusion, we're still 10x slower than naive C. :-( You can console yourself that maybe 5 in the ByteString paper and in Parallel Arrays paper you can find that difference between Haskell and C code may be hundreds times, so this is definitely an improvement. all the words about haskell being as fast as C is just propaganda :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] #haskell works
Hello Dan, Friday, December 14, 2007, 11:57:38 PM, you wrote: to allocate registers do exist. So I'm looking forward to the next version of GHC matching C's performance for inner loops of array manipulation code :-) with support of loop unrolling, smart register allocation, strength reducing and so on? :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On Dec 15, 2007 12:00 AM, David Menendez [EMAIL PROTECTED] wrote: These can (and, if Val is a newtype, will) be compiled to the same code, but they don't have the same type. In particular, there is no way to unify a - a with f a - f b for any f. Thanks for noticing that! I hadn't seen before that the two Val constructors in fmap f (Val x) = Val x were of different types. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On 12/14/07, David Menendez [EMAIL PROTECTED] wrote: And yes, I'm pretty sure that's the only possible implementation for that type which satisfies the functor laws. Lets just prove it, then; I'm pretty sure it comes pretty easily from the free theorem for the type of fmap. data Val a = Val Int fmap :: (a - b) - (Val a - Val b) which must satisfy the law fmap id1 = id2 with id1 :: forall a. a - a id2 :: forall a. Val a - Val a Now, first note that since we cannot make any choices based on the type of f, there's no way for f to be relevant to the result of fmap; we have no way to get something of type a besides _|_ to pass to f, and no use for things of type b. Therefore, since the choice of f can't affect the implementation of fmap, we are given the only possible implementation directly from the Functor law: fmap _ ~= id or, to avoid the type error mentioned previously, fmap _ (Val x) = (Val x) -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On Dec 15, 2007 3:44 AM, Benja Fallenstein [EMAIL PROTECTED] wrote: Hmmm. Something about that ticks off my don't play fast and loose with bottom detector. I should add that I do think you're correct if you ignore the existence of bottom, and I'm pretty sure that you're correct if you allow bottom but consider seq to be only slightly better than unsafePerformIO. But I couldn't turn your proof sketch into something that would completely convince me, myself :-) - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Execution of external command
On Dec 14, 2007 10:38 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: hUnsafeGetContentsDontUseThisUnlessYouHaveSpentThreeMonthsLearningGHCsExecutionSemanticsOrYouWillRegretIt i have more advanced proposal - we should include in its name whole paper on its semantics so anyone using it will be clearly warned. moreover, any suggestion to use this function will automatically include exact description of its caveats that is again The Right Thing To Do :) Until, that is, the first library appears on Hackage that aliases the name to ohBugger :-) - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Software Tools in Haskell
On Dec 14, 2007 9:29 AM, Henning Thielemann [EMAIL PROTECTED] wrote: I remember there was a discussion about how to implement full 'wc' in an elegant but maximally lazy form, that is counting bytes, words and lines in one go. Did someone have a nice idea of how to compose the three counters from implementations of each counter? I'm afraid one cannot simply use the split and count fragments trick then. Could you turn the folds into scans and use zip3 and last? I.e., something like this: data Triple a b c = Triple !a !b !c deriving Show countChars :: String - [Int] countChars = scanl (\n _ - n+1) 0 countChar :: Char - String - [Int] countChar c = scanl (\n c' - if c == c' then n+1 else n) 0 countLines = countChar '\n' countWords = countChar ' ' last' [x] = x last' (x:xs) = x `seq` last' xs zip3' (x:xs) (y:ys) (z:zs) = Triple x y z : zip3' xs ys zs zip3' _ _ _ = [] wc :: String - Triple Int Int Int wc xs = last' $ zip3' (countChars xs) (countWords xs) (countLines xs) main = print . wc = getContents (or use Data.Strict.Tuple -- but that only has pairs and no zip...) - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] #haskell works
On 12/14/07, Andrew Coppin [EMAIL PROTECTED] wrote: Well anyway, a few years ago we didn't have fusion, This is not true. Shortcut deforestation (fusion) has been in GHC for at least fourteen years: http://citeseer.ist.psu.edu/gill93short.html It's true that we didn't have stream fusion a few years ago. and we didn't have ByteString. (true.) [snip] All I know is that once again, it seems Haskell isn't as fast as I thought... *sigh* No, what you know is that *one particular implementation* of Haskell isn't as fast as you thought. [snip] A few years ago, the program would have taken 0.35 seconds. The end. I would be careful about making this statement if I were you. Did you actually try running the same code in GHC 5.0? It's not as if GHC didn't implement *any* optimizations in 2003 (you said above that 0.35 seconds was the result you got with -O0.) Cheers, Tim -- Tim Chevalier * catamorphism.org * Often in error, never in doubt Now, don't bother to flame me, because by the time you read this post I will be a different person from the one who wrote it. You cannot step in the same river twice. -- Sarah Barton ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] #haskell works
On 12/14/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Dan, Friday, December 14, 2007, 11:57:38 PM, you wrote: to allocate registers do exist. So I'm looking forward to the next version of GHC matching C's performance for inner loops of array manipulation code :-) with support of loop unrolling, GHC calls this inlining. smart register allocation, This is being worked on actively, AFAIK. strength reducing Easy to implement (in theory) with GHC rewrite rules, AFAIK (or at least, Simon PJ suggested that that might be so in a mailing list post a few months ago.) Cheers, Tim -- Tim Chevalier * catamorphism.org * Often in error, never in doubt People tell me I look down / but I'm always standing sixty-six inches off the ground. -- Carrie Bradley ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] #haskell works
On 12/14/07, Dan Piponi [EMAIL PROTECTED] wrote: There have been some great improvements in array handling recently. I decided to have a look at the assembly language generated by some simple array manipulation code and understand why C is at least twice as fast as ghc 6.8.1. One the one hand it was disappointing to see that the Haskell register allocator seems a bit inept and was loading data into registers that should never have been spilled out of registers in the first place. Someone who knows the backend better than I do can correct me if I'm wrong, but it's my understanding that GHC 6.8.1 doesn't even attempt to do any register allocation on x86. So -- register allocator? What register allocator? But this is being actively worked on; I understand there's code for it in the HEAD. On the other hand, the code wasn't fundamentally doing anything weird (eg. it wasn't doing graph reductions or anything like that, it looked like the sort of loop you might get from a C compiler). It was a few seconds of fairly mindless work to fix up the assembly language and make it much faster. And if I can do it, it means that the next generation of Haskell compiler should be able to do it too, after all, good freely available methods to allocate registers do exist. So I'm looking forward to the next version of GHC matching C's performance for inner loops of array manipulation code :-) It sounds like Team GHC is thinking about the exact same things you are here: http://hackage.haskell.org/trac/ghc/wiki/Status/Nov07 Cheers, Tim -- Tim Chevalier * catamorphism.org * Often in error, never in doubt Science fiction is not predictive; it is descriptive. --Ursula K. Le Guin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Questions about the Functor class and it's use in Data types à la carte
On Dec 14, 2007 9:44 PM, Benja Fallenstein [EMAIL PROTECTED] wrote: data Val a = Val Int instance Functor Val where fmap f (Val x) = f `seq` Val x Ah, good old seq. How I loathe it. Seriously, though, good catch. I always forget about seq when I'm doing stuff like this. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] #haskell works
Hello Tim, Saturday, December 15, 2007, 7:10:26 AM, you wrote: with support of loop unrolling, GHC calls this inlining. 1. loop unrolling means generating several iterations of loop body, so that, say, 100 iterations of *p++=*q++ becomes 25 iterations of *p++=*q++; *p++=*q++; *p++=*q++; *p++=*q++; 2. actually, ghc can't inline tail-recursive functions at all (although i don't checked this after 6.4) there are also many more optimization tricks. i don't think that modern compiler with optimization level comparable to gcc can be delivered without many man-years of development -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
