June 2004 - Haskell-Cafe

Audio signal processing in Haskell
by Henning Thielemann 02 Jul '04

02 Jul '04

As I can see a question similar to mine was already raised here: http://www.haskell.org/pipermail/glasgow-haskell-users/2004-February/006305… I also encountered the elegance that Haskell's laziness provides for signal processing. I use lists for the signals. With help of Haskore I put together a small song and it needed 5 minutes for rendering the quite simple music of about 30 seconds. Don't care about the exact numbers but I find it rather slow. What is the most promising strategy to speed up the computation without loosing the elegance of Haskell's lists? 1. Upgrading GHC from 6.0 to the current version? 2. Use of simplification rules? How can I find out what new rules may be useful? The several dumps that GHC can generate are a bit hard to understand. :-( Is there some more detailed information about what rules GHC already applies than what one can get with -ddump-simpl-stats and -ddump-rules? 3. More strictness? Is a custom list structure with strict entries and maybe with only one constructor (thus always infinite) a considerable alternative? This would disallow the use of lots of functions that deal with lists, including State monad functions. 4. A list of arrays? Then signal processes with feedback like an echo are much more difficult.

2 3

Relating functors in Category Theory to Functor
by David Menendez 02 Jul '04

02 Jul '04

Until recently, I've had difficulty relating the concept of a "functor" from Category Theory to the class Functor in Haskell. I've figured out a relationship that seems to make sense, but I wanted to check with the list to make sure I'm not on the wrong track. In Category Theory, a functor F between categories C and D has two parts: (1) a mapping F[ob] from the objects of C to the objects of D (2) a mapping F[mor] from the morphisms of C to the morphisms of D For any morphism f: a -> b in C, there is a morphism F(f): F(a) -> F(b) in D. For two morphisms f and g in C, F(f . g) = F(f) . F(g) in D. We can interpret Haskell as a category with types as objects and functions as morphisms. For example, isDigit :: Char -> Bool. So, for some Functor f, the type constructor f corresponds to F[ob], and fmap to F[mor]. For any function g :: a -> b, fmap g :: f a -> f b, and fmap (g . h) = fmap g . fmap h. -- For two functors F, G: C -> D, there is a natural transformation tau from F to G, if for every object a in C, there is morphism tau[a]: F(a) -> G(a) in D. In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a]. -- A monad is a functor, F: C -> C, plus two natural transformations mu: F^2 -> F and eta: I -> F (I being the identity functor for C). In Haskell, F[ob] becomes the type constructor, F[mor] becomes fmap (or liftM), mu becomes join :: f (f a) -> f a, and eta becomes return :: a -> f a. So, am I on the right track here? -- David Menendez <zednenem(a)psualum.com> <http://www.eyrie.org/~zednenem/>

5 6

Re: [Haskell] Help in understanding a type error involving forall and class constraints
by Duncan Coutts 30 Jun '04

30 Jun '04

On Wed, 2004-06-30 at 12:00, MR K P SCHUPKE wrote: > Ahh.. I see whats happening: > > MArray (STUArray s) a (ST s) => String -> String -> ST s (UArray (Int,Int) a) > > IArray UArray a => String -> String -> a > > nothing here is specifying a... you cannot leave a polymorphic in this case. > > You need to supply the constraint "MArray (STUArray s) a (ST s)" to distString > but "s" is not in context... Right, because the return type of distString Int is an instance of MArray. But if we try to make 'a' polymorphic then we can't specify the constraint because it involves 's'. So the obvious follow-on question, is is there any intermediate point where 's' is in scope where we can supply a type annotation to supply the context or is it simply impossible? To restate the question for Haskell-Cafe readers: Is it possible to return an arbitrary unboxed array that was constructed in the ST monad (as an STUArray)? The issue is that you end up with a MArray class constraint that involves the state thread's 's' parameter, but this type variable gets 'hidden' by runST which universally quantifies over it. runST :: forall a. (forall s. ST s a) -> a Duncan

1 1

Switching monadic encapsulations
by Graham Klyne 28 Jun '04

28 Jun '04

Is there a function that switches monadic layering? f :: (Monad m1,Monad m2) => m1 (m2 a) -> m2 (m1 a) Does this even make sense in the general case? I'm thinking along the lines of a generalization of sequence to non-list monads. This question arises from a desire to generalize some error handling code, starting with: liftES :: (a->Either String [a]) -> Either String [a] -> Either String [a] where (Either String) as used as an error monad. A simple implementation of this might be: liftES _ (Left er) = Left er liftES f (Right as) = sequence $ map f as but I notice that liftES looks a little bit like liftM, and sequence does for the List monad what I am seeking to generalize: sequence :: [m a] -> m [a] and map looks like a version of liftM specialized to lists: liftM f = \a -> do { a1 <- a ; return (f a1) } = \a -> ( a >>= \a1 -> return (f a1) ) when m is a list monad: = \a -> concat (map (\a1 -> [f a1]) a) Similarly, concat appears to be a monadic join on lists. My listES might be partially generalized to something like: liftX :: (r -> m [r]) -> m [r] -> m [r] liftX mf = \mb -> do { b1 <- mb ; liftM concat $ sequence $ map mf b } the liftM here being used to apply 'concat' to achieve m [[r]] -> m [r]. I can see a possible replacement of concat with join and map with liftM, but I don't see any purely monadic equivalent for 'sequence'. Hence the original question. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 2

RE: [Haskell-cafe] readEitherChan
by Simon Marlow 28 Jun '04

28 Jun '04

On 25 June 2004 21:20, S. Alexander Jacobson wrote: > On Fri, 25 Jun 2004, Simon Marlow wrote: >> It seems to me that with MVars you can implement pretty much any >> abstraction you need, including choice, and it's not clear that there >> would be any advantage to providing any more primitives. That's >> based on my experience so far, anyway - I know there are people out >> there that have made rather more heavy use of MVars than I have (eg. >> George Russell). > > Well we appear to be having a problem implementing > a takeEitherMVar or readEitherChan without adding > a new abstraction.... I strongly suspect that it can't be done, at least not if you want to have (a) non-busy waiting, and (b) async exception safety. My point was that I believe in order to support takeEitherMVar as a primitive, we would have to add essentially the same machinery to MVars that you would need if you were to implement it as an abstraction on top of MVars in Haskell. Cheers, Simon

1 0

RE: [Haskell-cafe] need help on exercise
by Graham Klyne 28 Jun '04

28 Jun '04

Your problem seems to be related to the Num class, and the fact that the compiler can't figure out what '5' is -- see pp 223/224 of Simon Thompson's book. The code below offers two possible resolutions, one commented: [[ class Show a => Visible a where toString :: a -> String size :: a -> Int toString x = show x size x = 1 {- instance Visible Int where toString x = show x size _ = 1 -} instance Num a => Visible a where toString x = show x size _ = 1 {- t1 - toString (5::Int) -} t1 = toString 5 ]] #g -- At 23:58 27/06/04 -0400, kasager wrote: >Hi, in my last posting i asked for help with exercise 12.5 however, i forgot >to give my code... here is my code and the error messege that hugs gives when >i try to run it (it compiles fine, however when i test it, it gives an >error)... > >Code: > >class Show a => Visible a where > toString :: a -> String > size :: a -> Int > > toString x = show x > size x = 1 > >instance Visible Int where > toString x = show x > size _ = 1 > >-- i have tried writing this without the show function, and the same error >messege still is given... i also have other instances in the class, which >work >fine and should not effect this issue... > >Error: > >Prelude> :l "C:\\WorkArea\\Haskell\\homework\\ch12_5.hs" >Main> toString 5 >ERROR - Unresolved overloading >*** Type : (Num a, Visible a) => [Char] >*** Expression : toString 5 > > >If you can help in any way or give any suggestions its greatly appreciated... >once again thanks much. ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

need help on exercise
by kasager 26 Jun '04

26 Jun '04

Hi, I am working on exercise 12.5 from "Haskell, The Craft of Functional Programming, second edition" by Simon Thompson. It asks to make Int an instance in the Visible class. I have tried multiple ways of doing this however I keep receiving the same error messege when I compile my program, saying that my types do not match and i have given a (Num a, Visible a) => String, when it is supposed to be an Int -> String. If anyone could help me with this issue it would be greatly appreciated. Thanks, Kelly

2 1

RE: [Haskell-cafe] readEitherChan
by Simon Marlow 25 Jun '04

25 Jun '04

On 24 June 2004 21:24, S. Alexander Jacobson wrote: > Cool! Why does it have an efficiency problem? Because it does busy-waiting. > And I would also observe that this solution > doesn't work for readEitherChan because there is > no tryReadChan. The naive tryReadChan > > tryReadChan chan = if isEmptyChan chan then return Nothing else > return $ readChan chan > > leaves you vulnerable to race conditions. > > It looks like we have now have two very similar > functions that, because they need the concrete > representation, need to be added in the library: > tryReadChan and tryReadSampleVar. > > Is there a systemic reason why these two very > similar functions are absent? There is no point > in my trying to add them if there is some *in > principle* difficulty. There's no fundamental difficulty that I'm aware of. The lack of these functions is probably down to historical reasons: tryTakeMVar and tryPutMVar are recent additions to the old MVar interface. > The concurrent paper seems > to indicate that there is something fundamentally > suspect about a choice operator as a primitive. > Is that issue related? The argument is based on the difficulty of implementing choice in a multithreaded or distributed setting, and the fact that simplifications to make the implementation easier tend to interfere with abstraction. It seems to me that with MVars you can implement pretty much any abstraction you need, including choice, and it's not clear that there would be any advantage to providing any more primitives. That's based on my experience so far, anyway - I know there are people out there that have made rather more heavy use of MVars than I have (eg. George Russell). > Also, you wouldn't need these functions if > Haskell's concurency model was defined to be > non-preemptive. How come forkIO was not > specifically defined to be non-preemptive (with > forkOS dependent on the local OS native threading > model)? So threads forked by forkIO would be non-preemptive with respect to what? Other threads forked by forkIO, or forkOS? forkOS is a very recent addition, BTW. Its primary purpose is to make a "bound" thread, to give the programmer a handle on which OS thread is used to make foreign calls. See this paper we submitted to the Haskell Workshop this year: http://www.haskell.org/~simonmar/papers/conc-ffi.ps.gz Hope that sheds some light. Cheers, Simon

2 1

RE: [Haskell-cafe] Haskell and concurrency
by Simon Marlow 25 Jun '04

25 Jun '04

On 25 June 2004 11:52, Graham Klyne wrote: > Anyway, I was wondering if any of the work on concurrent Haskell or > concurrent functional programming addresses similar systems or ideas, > in which implementation/hardware concurrency is decoupled from > application concurrency requirements, and particularly with a view to > applications requiring very low-overhead fine-grained concurrency? Concurrent Haskell is designed to provide exactly the kind of lightweight concurrency you're after. It won't be as quick as a custom application-specific threading model in the way you describe, but it's a *lot* faster than using one OS-thread for each thread in your system. And if you find it to be still too slow for your application, we know of several ways to speed it up... Cheers, Simon

2 1

RE: [Haskell-cafe] how to get started: a text application
by Bayley, Alistair 25 Jun '04

25 Jun '04

> From: Max Ischenko [mailto:max@ucmg.com.ua] > > Well, yes. In Markdown, like in most other "rich-text" > formats symbols are overloaded a lot. After all, it has to > constrain itself to "plain text". > > I'm going to try a "two-stage tokenization" (not sure how to > name this correctly). Basically, first I'd split the raw text > into "symbols" (like space, char, digit, left-bracket) and > then turn these symbols into tokens (like paragraph, > reference, start bold text, end bold text, etc.) Markdown looks a lot like Wiki source to me i.e. it looks like the text source for a Wiki page. It seems to serve the same purpose i.e. well-formatted plain text intended for conversion to HTML. Many (most?) Wiki engines use straightforward regex substitution to convert the text source into HTML, rather than implement a lexer/parser/pretty-printer combination. Obviously this makes for a fairly simple implementation. Mind you, some of the regex's are quite complex... See, for example: Source for Moin-moin, which runs the Haskell wiki: http://cvs.sf.net/viewcvs.py/moin/MoinMoin/parser/wiki.py?view=markup Original c2.com wiki (actual source a bit hard to find): http://www.c2.com/cgi/wiki?TextFormattingRegularExpressions ... which leads to: http://www.c2.com/cgi/wiki?TextFormattingRegularExpressionsDiscussion http://www.c2.com/cgi/wiki?AlternativesToRegularExpressions ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

3 3