- Haskell-Cafe - Haskell.org

A type class puzzle
by Yitzchak Gale 12 Nov '06

12 Nov '06

Consider the following sequence of functions that replace a single element in an n-dimensional list: replace0 :: a -> a -> a replace0 = const replace1 :: Int -> a -> [a] -> [a] replace1 i0 x xs | null t = h | otherwise = h ++ (replace0 x (head t) : tail t) where (h, t) = splitAt i0 xs replace2 :: Int -> Int -> a -> [[a]] -> [[a]] replace2 i0 i1 x xs | null t = h | otherwise = h ++ (replace1 i1 x (head t) : tail t) where (h, t) = splitAt i0 xs etc. Generalize this using type classes.

8 14

(twice head) && (twice tail)
by Greg Buchholz 12 Nov '06

12 Nov '06

Over on comp.lang.functional ( http://xrl.us/s6kv ), Toby Kelsey is wondering about writing a function "twice" that applies a function to an argument two times... > twice' :: (a -> a) -> a -> a > twice' f x = f (f x) ...that works for things like "twice succ 0" and "twice tail [1,2,3]", but the type signature means you can't try something like "twice head [[1]]". You can get the "twice head" case to work with a function like... > twice'' :: (forall a. (m a) -> a) -> (m (m b)) -> b > twice'' f x = f (f x) ...and if you want something like "twice (flip (:) [])", you'd use... > twice''' :: (forall a. a -> (m a)) -> b -> (m (m b)) > twice''' f x = f (f x) ...it seems like those type signatures have at least a passing resemblance, so I was wondering if you could use type classes to combine these functions. I tried something like... > class Twice a b c | a b -> c where > twice :: a -> b -> c > > instance Twice (a->a) a a where > twice f x = f (f x) > > instance Twice (forall a. (m a) -> a) (m (m b)) b where > twice f x = f (f x) ...but with ghc-6.6 it chokes with... Illegal polymorphic or qualified type: forall a. m a -> a In the instance declaration for `Twice (forall a. (m a) -> a) (m (m b)) b' ...I can't say I'm surprised, but I was wondering if anyone else has thoughts on how this limitation might be worked around. Curious, Greg Buchholz

2 1

Simple implementations of the lambda calculus
by Lennart Augustsson 12 Nov '06

12 Nov '06

Some time ago I made a little experiment and implemented an interpreter for the lambda-calculus in Haskell. The only reason was that I wanted to try different ways of doing it. So I did it using simple substitution (i.e., as the textbooks describe it), unique identifiers, deBruijn indicies, and higher order abstract syntax. You can get the code from http://darcs.augustsson.net/Darcs/Lambda/ or just check out small paper at http://darcs.augustsson.net/Darcs/ Lambda/top.pdf -- Lennart

1 0

Re: Livecoding music in Haskell
by Rohan Drape 11 Nov '06

11 Nov '06

On Tue Nov 7 16:32:11 EST 2006, alex wrote: > The way I see it there are two big issues - the first is drift and the > second is latency. As hinted at when Alex's work was discussed last November: "OSC messages can be timestamped, and SuperCollider has a sample accurate scheduling queue, so language timing jitter can easily be worked around." http://www.haskell.org/pipermail/haskell-cafe/2005-November/012483.html Currently Sound.SC3 has a procedure 'at' that can be used for scheduling. This procedure doesn't really belong in Sound.SC3, and ought probably be taken out. Still, with the current darcs repository the following makes a ping every second, on the second, sample accurately, for half a minute. If you run the binary twice the pings will be twice the amplitude, no phase errors - fingers crossed. import Sound.SC3 import Control.Concurrent (forkIO) ping f a = out 0 (sinOsc AR f 0 * e) where c = EnvNum (-4.0) e = envGen KR 1 a 0 1 removeSynth (envPerc 0.1 0.6 1 [c,c]) latency = 0.01 bundle t m = OscB (t + latency) m pinger = do now <- utc at (fromIntegral (ceiling now)) f where f t = do fd <- sc send' fd (bundle t [s_new "ping" (-1) AddToTail 1]) putStrLn "Sending ping" return 1.0 main = do fd <- sc putStrLn "Sending Ping Instrument" sync' fd (d_recv' "ping" (ping 440 0.1)) putStrLn "Resetting scsynth" reset fd putStrLn "Starting schedule thread" forkIO pinger putStrLn "Delaying main thread" pause 30 putStrLn "End of delay, exiting" The above assumes that scsynth is running on the local host at the standard port, 57110, and that the GHC runtime scheduler jitter plus localhost network latency for this task is below 0.01 seconds, which is true on my otherwise idle X31 at 600MHz - this is not at all bad, I am impressed in any case - setting latency to zero gives reports from scsynth of: > late 0.008414722 > late 0.006882722 > late 0.005348722 > late 0.003815721 > late 0.002282721 > late 0.000748721 Tacked on below, for interested readers, are some notes on a related scheme scheduler, the notes were written in response to a related query about scheme & scsynth some time ago. The relation to the haskell above is pretty straightforward, the haskell 'at' discards the notion of a mutable schedule - with cheap concurrency such a thing is of arguable use - and the haskell 'at' ought to allow the event generator to return Nothing to stop scheduling. Regards, Rohan ++ Simple sample accurate scheduling from runtimes with moderate scheduling jitter is straightforward using SuperCollider. One simple model is: (at Q TIME (lambda (t f) (EVENT t) (f DELTA))) at = the scheduler interface Q = a <schedule> value TIME = a UTC timestamp t = the scheduled UTC time (ie. TIME or subsequent delta), regardless of when the procedure actually runs f = a rescheduling function that in effect does (at Q (+ t DELTA) *SELF*) EVENT = the action, usually constructs an osc bundle and sends it to scsynth DELTA = the delta time to reschedule to, to not re-schedule just don't call f The EVENT sends a bundle to scsynth and adds latency as required so that the scheduled bundle arrives ahead of the timestamp, the actual sample-accurate scheduling is handled by a queue at scsynth. The example below will schedule a ping at each whole second, and the scheduling will be sample accurate so long as the scheme runtime jitter is less than 0.1 seconds minus the network latency to get a UDP packet to the scsynth address. Here (utc) gets the current time, (-> s p) sends an OSC packet p to the server s, (/s_new ...) makes a /s_new OSC message, & (bundle t m) makes an OSC packet converting the UTC timestamp to NTP. (define s (open-udp* "127.0.0.1" 57110)) (define Q (make-schedule*)) (define L 0.1) (define (ship t m) (-> s (bundle (+ t L) m))) (at Q (ceiling (utc)) (lambda (t f) (ship t (/s_new "ping" -1 1 1)) (f 1.0))) Obviously to schedule just one ping in five seconds time: (at Q (+ (utc) 5) (lambda (t _) (ship t (/s_new "ping" -1 1 1))))

2 3

Great language shootout: reloaded
by Isaac Gouy 11 Nov '06

11 Nov '06

Donald Bruce Stewart wrote: -snip- > I agree. Breaking the rules was mainly the reason for the drop. Entries > like chameneos and fasta. Also, the other language teams kept improving > things. Yes, I missed that opportunity for listing things in threes ;-) Over the year improved programs were contributed for other languages. In contrast to the last focussed effort by the Haskell community, many of the other programs are contributed by individuals working alone, over many weeks. > > Other language (perl, iirc) were affected far worse by the gzipping. > gzip is an interesting measurement, and it doesn't hurt Haskell too much > either way -- short Haskell programs stay short when compressed. > > As a result, rewriting verbose entries to ByteString will probably be > much more useful :) > > Btw, Isaac, are we going to have any new parallelism benchmarks? I'd > love to try out the SMP runtime ;) If we were to have a 'which is the silliest comparison on the computer language shootout' competition, I think chameneos and cheap-concurrency would be joint first - there are so many really really different approaches. Ideas for unicode text processing would be more welcome. ____________________________________________________________________________________ Cheap talk? Check out Yahoo! Messenger's low PC-to-Phone call rates. http://voice.yahoo.com

1 0

Automatic fixity allocation for symbolic operators
by Brian Hulley 11 Nov '06

11 Nov '06

Hi - I'm wondering if it is possible to construct a methodical procedure to assign a fixity to symbolic operators so that we could get rid of the need for user defined fixites. User defined fixities are an enormous problem for an interactive editor, because it is not possible to construct a parse tree of some code if you don't know what the fixities are, and an editor must be able to do something useful with a code fragment without having to look inside other modules (because the other modules may not yet have even been written!). Also, the programmer or reader of code needs to be able to understand each code fragment independently as well. >From the Haskell98 report, the Prelude defines: infixr 9 ., !! infixr 8 ^, ^^, ** infixl 7 *, /, `quot`, `rem`, `div`, `mod` infixl 6 +, - infixr 5 :, ++ infix 4 ==, /=, <, <=, >=, > infixr 3 && infixr 2 || infixl 1 >>, >>= infixr 1 =<< infixr 0 $, $!, `seq` Suppose we ignore the varid operators and just consider the symbolic ops. What I'm trying to find is a systematic way to assign fixities to all other possible sequences of symbol characters that is consistent with what we've already got in the Prelude. As a first step, we could say that "mirrored" operators must share the same precedence ie: =<< >>= < > For associativity, we could assign each character an associativity weight: -1 left associative 0 neutral 1 right associative and say that the associativity is simply the sign of the sum of the associativity weights of the characters thus: > -1 = 0 < 1 =<< 0 + 1 + 1 ie infixr Note that I don't care about non-associative ops since the non-associativity of something should be a question for the type checker not the parser imho - ideally we should be able to create a parse tree for any possible operator expression. To form the precedence, we could assign each character a precedence value eg: 9 . ! 8 ^ 7 * / 6 + - 5 : 4 = 3 & 2 | 1 < > 0 $ A first attempt might be to say that the precedence is simply the decimal expansion of the precedence values eg >>= has precedence 1.14 and $! has precedence 0.9. However, as noted above, mirrored ops must share the same precedence so an alternative is to create some ordering of characters such that when the set of characters in an operator is sorted according to this ordering, the decimal expansion of the precedence digits will give the same relative ordering for operator precedences as the Prelude. For example, using $ | & + - * / ^ . ! : < > = as the ordering, we'd get: infixr 9 . !! 9 9.9 infixr 8 ^, ^^, ** 8 8.8 7.7 infixl 7 *, /, 7 7 infixl 6 +, - 6 6 infixr 5 : , ++ 5 6.6 infix 4 ==, /=, <, <=, >=, > 4.4 7.4 1 1.4 1.4 1 infixr 3 && 3.3 infixr 2 || 2.2 infixl 1 >>, >>= 1.1 1.14 infixr 1 =<< 1.14 infixr 0 $, $! 0 0.9 Although most existing ops get a similar precedence (eg ^ ^^ and ** are all still in the same group relative to the other ops despite the fact that within the group there is now an ordering) the main problem seems to be that < <= >= > get precedences that bind too loosely and /= is totally wrong. This problem aside, the above algorithm would give sensible precedences for such things as: :> <: 5.1 <+> <*> 6.11 6.11 where the use of <> neutralizes the associativity contribution of < or > respectively (since (-1) + 1 == 0), giving us the intuitive associativity we'd expect from the "interesting" character in the middle. (The problem of /= getting 7.4 could be solved by putting / after = in the order, to get 4.7, but unfortunately this would mean that since <> must be before =, <> would be before / so </> would get the wrong precedence compared to <*>) Another issue is that there is no assignment of associativity weights such that "*" is infixl but "**" is infixr (ditto + and ++) so perhaps we'd need to associate each character with an associativity function. Similar to precedences, we then define an associativity ordering and let the resulting associativity be the sign of the composition of the sorted functions applied to 1 eg: ^ const (-1) * \x -> x * (-1) = id & const (-1) < (+1) > (+ (-1)) Then * (\x -> x * (-1)) 1 === -1 ie left ** (\x -> x * (-1)) . (\x -> x * (-1)) $ 1 === +1 ie right >>= > > = (+ (-1)) . (+ (-1)) . id $ 1 === -1 <*> -- remember ordering * < > (\x -> x * (-1)) . (+1) . (+ (-1)) $ 1 === ((1 - 1) + 1) * (-1) === -1 ie left as required!!! :-) Anyway this is as far as I've got so far trying to rationally reconstruct the original Prelude precedences to achieve the golden aim of eliminating the infinite problem of fixity declarations from source code... :-) (Regarding `div` `seq` etc - I'd just assign them all the same precedence because use of multiple varid ops in the same expression with different precedences, or trying to combine them with symbolic ops, is just a highway to confusion city imho. Note also that (seq x $ exp) is not only clearer but is also one character shorter than (x `seq` exp)) The main open problem is finding an algorithm which assigns a good precedence to >>= as well as to >= and /= and </> and <*>.... ;-) Any ideas? Thanks, Brian. -- www.metamilk.com

21 57

Announcement: new maintainers forr wxHaskell
by Jeremy O'Donoghue 11 Nov '06

11 Nov '06

Hi all, I'd like to announce that we have a new team of maintainers in place for wxHaskell, so we're hoping that this list will see a significant increase in activtiy in the future. We have several near-term objectives, which will likely occur in roughly the order below: * Pull together all of the patches for various wxHaskell functionalities which are 'out there' into the core distribution. * Enhance support for Unicode. * Ensure that we support GHC 6.4.2 and GHC 6.6. * Add support for wxWidgets 2.6.3 and maintain support for wxWidgets 2.4.2. There are very good reasons why many wxHaskell users will want to continue to use 2.4.2. * 'Cabalize' the wxHaskell build system. * Add new examples and increase the coverage of different wxWidgets functionalities. * Create binary releases / installable packages for popular platforms (Windows, Mac, Debian are current favourites) The maintainers will work mainly on a public Darcs repository at http://darcs.haskell.org/wxhaskell, which will always contain the latest patches, but which may not always be stable. I will, from time to time, release reasonably stable updates of files to Sourceforge CVS, and we will aim for binary releases whenever this makes sense. I'd ask the community to send patches via this list. They will get added to the public Darcs repository once at least one of the maintainers has successfully integrated and built them. We will create a separate developers list if the volume of patches ever threatens to overwhelm the wxhaskell-users list :-) To go with the above, I hereby provide first patch to to the archive at http://darcs.haskell.org/wxhaskell as an attachment. This patch brings together patches from a number of sources (mainly Shelarcy and Eric) to provide some support for Unicode variants of wxWidgets, a couple of extra widgets, preliminary support for wxWidgets 2.6.3 and a patch to enable build with GHC 6.6. None of this would have been possible without a great bunch of volunteers who have come forward and shown great patience with the slow pace at which I have pulled this together. Eric Kow, Shelarcy, Mads Lindstrøm, Time Docker and Frank Berthold have all offered their assistance, and should take a virtual bow. Finally, none of this would have been possible without the assistance of Daan Leijen, the original author of most of wxHaskell, who has been gracious enough to offer advice, and to pass on everything we need to move forward.

4 3

aggressiveness of functional dependencies
by Nicolas Frisby 11 Nov '06

11 Nov '06

I have a question about functional dependencies, instance contexts, and type inference. A specific example and question is in the attached code. In brief the question is: to what degree does type inference use the functional dependencies of an instance's class and context? I believe I am wishing it were more aggressive than it is. Please note that I have not enabled overlapping instances. Any suggestions regarding how to get the inferred type of |rite_t1| to be the one I anticipated would be much appreciated. Of course, I would also appreciate explanations of why I shouldn't anticipate it! The rest of this message is a copy of the attached code. Thanks, Nick I'm using GHC 6.6, but I see the same inferred types with 6.4.1. > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} -- for the coverage condition > > module FunDepEx where A plain ole' isomorphism class. > class Iso a b | a -> b, b -> a where > rite :: a -> b > left :: b -> a Isomorphism lifts through the sum bifunctor. > bifmap_either f g = either (Left . f) (Right . g) > > instance ( Iso f f', Iso g g' > ) => Iso (Either f g) (Either f' g') where > rite = bifmap_either rite rite > left = bifmap_either left left Some types to play around with. > newtype MyChar = MyChar Char deriving (Show, Eq) > > instance Iso MyChar Char where > rite (MyChar c) = c > left c = MyChar c > instance Iso Char MyChar where > rite c = MyChar c > left (MyChar c) = c My type inference confusion follows; the unit arguments are just to suppress the monomorphism restriction. > t1 :: Either Char a > t1 = Left 'c' > > rite_t1 () = rite t1 The inferred type for rite_t1 is rite_t1 :: (Iso (Either Char a) (Either f' g')) => () -> Either f' g' Why isn't the inferred type of rite_t1 the same as the ascribed type of rite_t1'? > rite_t1' :: Iso b b' => () -> Either MyChar b' > rite_t1' () = rite t1

2 5

Great language shootout: reloaded
by Isaac Gouy 11 Nov '06

11 Nov '06

> On 11/10/06, Henk-Jan van Tuyl <hjgtuyl at chello.nl> wrote: >> >> Haskell suddenly dropped several places in the overall socre, when the >> size measurement changed from line-count to number-of-bytes after >> gzipping. Maybe it's worth it, to study why this is; Haskell programs >> are >> often much more compact then programs in other languages, but after >> gzipping, other languages do much better. One reason I can think of, is >> that for very short programs, the import statements weigh heavily. Before this gets out-of-hand, my memory is certainly fallible but as I recall Haskell /did not/ drop several places because size measurement changed from line-count to gzip byte-count. 1) Check the webpage that Don Stewart cached and note the values for the memory use and code-lines multipliers, and note the values for the benchmark weights http://www.cse.unsw.edu.au/~dons/data/haskell_1.html Now go to the computer language shootout website and note the multipliers and benchmark weights. 2) Some Haskell programs were pushed into 'interesting alternative implementations' because they'd strayed so far from the spirit of the benchmark. (It takes a while for people to notice and complain, but eventually they do.) ____________________________________________________________________________________ Do you Yahoo!? Everyone is raving about the all-new Yahoo! Mail beta. http://new.mail.yahoo.com

3 2

Template Haskell.
by szefirov＠ot.ru 10 Nov '06

10 Nov '06

Why doesn't reify return function body? reify (mkName "somefunction") for a function defined in the same module returns constructor VarI (of data type Info) that does not contain function declaration in (Maybe Dec) part. What actions should I perform to get a function body with patterns, expressions and all that?

2 1