July 2004 - Haskell-Cafe

Re: [Haskell-cafe] newbie problems
by MR K P SCHUPKE 03 Jul '04

03 Jul '04

The zipper should work on n-ary trees. all the zipper does is store the tree as (Context,Subtree) so you just need to adapt that to a Rose-Tree. you could do something like (and I am thinking out loud here as I havent written zipper code for rose trees)... data Context x = Root | Parent x (Context x) [Rose x] [Rose x] data Rose x = Node x [Rose x] so at any given point in the tree the context is either Root, or the Parent (with the value at that node, the parents context, then the left siblings and right siblings as lists) As to the difference between types and values, a type limits the permitted values. For example a :: [Int] a is a list of integers. now data IntList = Value Int | List [Int] IntList can be a single int or a list of ints... data IntList = Value Int | List [IntList] Now intlist can be a value or a list of IntLists... we are dealing with the type of permitted data not the data itself. when we define a value for example: a :: IntList a = Value 3 This must obey the construction rules given in the data type "IntList" So you see when a data declaration refers to itself it is not a "pointer" but an inclusion of the type for example: a :: IntList a = List [Value 3,List [Value 2,Value 1],Value 4] is a valid instance of IntList, but notice that although the 'type' refers to itself the value is not self-referential. Thats not to say self referential values are not possible - but lets avoid confusing the issue with such things. Keean.

2 1

Running Total or Incremental Sum as a higher order type ?
by Crypt Master 03 Jul '04

03 Jul '04

Hi I was attempting to get a running a total of a list i.e for [1,2,3] the result should be [1,3,6] -- [1, 1+2, 2+3] I build this function: incrementalSum [] x = [] incrementalSum (x:xs) runningTotal = currentSum : incrementalSum xs currentSum where currentSum = runningTotal + x I was trying to see how I could higher order functions for this but came up empty. Surely this is a pattern which has been abstracted ? I feel I have missed the obvious here. Thanks, S _________________________________________________________________ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus

2 1

RE: [Haskell-cafe] List syntax -- [] vs ()
by Crypt Master 03 Jul '04

03 Jul '04

Hi Thanks. A light bulb just went on :). I am still in awe of how much "special syntax" is made of such simple base. Haskell certainly is an interesting thing to learn, its like fractals, complexity and beuty from simplicity. S ----Original Message Follows---- Crypt Master, CM> I have noticed that lists seem to swtich between CM> using [] and using (). for example: CM> CM> listSum [] = 0 CM> listSum (x:xs) = x + listsum xs The parentheses are just 'normal' parentheses that are needed because application binds stronger than (:). Without the parentheses, you would get listSum x : xs which is the same as (listSum x) : xs . HTH, Stefan _________________________________________________________________ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus

1 0

List syntax -- [] vs ()
by Crypt Master 03 Jul '04

03 Jul '04

Hi I have noticed that lists seem to swtich between using [] and using (). for example: listSum [] = 0 listSum (x:xs) = x + listsum xs but when specificy lists you use [] as in [1,2,3]. or type signatures are [a] -> [a] It also seems when they mentioned on the right hand side it also always []. Is it just for pattern matching that you use the "tuple" syntax ? How does haskell know we dont mean a tuple ? Or do we mean a tuple when we say (x:xs) ? Thanks _________________________________________________________________ MSN 8 with e-mail virus protection service: 2 months FREE* http://join.msn.com/?page=features/virus

2 1

Re: [Haskell-cafe] Newbie questions
by Crypt Master 03 Jul '04

03 Jul '04

Hi Thanks for responding and taking the time to respond so fully. Its much appreciated! >From what I can see, a key difficulty you're having is with the >"evolvepopulation" function. You've given it the type a -> a, which >pretty much requires it to be an identity function, because it's not >allowed to make any assumptions about the values it takes. I was going trying for generic as possible, I am keen to expore how much more expressive one can be in functional lanaguages. >To make things easier to read, try defining types for Population and >Individual (they can always be generalized later). > type Individual = Int > type Population = [Individual] A use fill tip, thanks. [Snip] >It looks like you're defining evolution as the composition of mutate, >cross, and select, but got tripped up by the order of evaluation. >Specifically, "mutate cross select p" is the same as "((mutate cross) >select) p", which probably isn't what you want. It only recently dawned on me that functions are left asscoaitive and your absolutly right its not what i had in mind. >If you have: > mutate :: Population -> Population > cross :: Population -> Population > select :: Population -> Population >Then you could define > evolve p = mutate (cross (select p)) > > -- alternative: > -- evolve = mutate . cross . select I now get what the f.g is as well :-) Thanks, the alternate format with the original has just clicked something else into place. >Starting from an initial population, you want to generate a sequence by >iterating evolve, starting from an initial population. Haskell provides >a function "iterate" for this purpose, or you can define your own. Yeah other posters suggested this as well. I now have the the same function as you mentioned which is very nice: gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom = iterate evolvePopulation [snip] >I found it helpful to remember that you can think of a function f :: a >-> b -> c as taking two arguments of types a and b and returning a >result c, or as taking a single argument of type a and returning a >result of type b -> c. Once you become comfortable with partial >application, a lot of Haskell code starts to make more sense. I understood the partial application when explained in simple terms, but I find I have a hard time when it used in more coimplicated examples. The currying in the "The Haskell School of Expression" left with a big "Huh", even though a simple application makes sense to me. "The craft of Functional Programming" it seesm thicker more methdoical, so I may get some more of the basics down in the next few weeks. Thanks again. ------------------------------ Message: 8 Date: Sat, 03 Jul 2004 08:38:55 +0000 From: "Crypt Master" <cryptmaster(a)hotmail.com> Subject: Re: [Haskell-cafe] Newbie questions To: duncan.coutts(a)worcester.oxford.ac.uk Cc: haskell-cafe(a)haskell.org Message-ID: <BAY18-F13KHmj9n1xxW00056ac5(a)hotmail.com> Content-Type: text/plain; format=flowed [Snip] People say function application in Haskell is written without brackets but this can be misleading, here you do need brackets to indicate that 'gaSolutionSpace [1,2,3,4,5]' is one argument and not two. So you should write: take 5 (gaSolutionSpace [1,2,3,4,5]) [Snip] Thanks alot, this was very helpfull. It also makes more sense now that I looked up the associativity of functions and found it to be left assoc. For some reason I assumed it would automaically bracket form the right as such (take (5 (gaSolutionSpace [1,2,3,4,5]))) but its actually this (((take 5) gaSolutionSpace) [1,2,3,4,5]) Thanks again. _________________________________________________________________ Tired of spam? Get advanced junk mail protection with MSN 8. http://join.msn.com/?page=features/junkmail ------------------------------ Message: 9 Date: Sat, 03 Jul 2004 08:46:24 +0000 From: "Crypt Master" <cryptmaster(a)hotmail.com> Subject: [Haskell-cafe] Re: Newbie questions To: wferi(a)afavant.elte.hu Cc: haskell-cafe(a)haskell.org Message-ID: <BAY18-F16gyf2M0KFHR000262c6(a)hotmail.com> Content-Type: text/plain; format=flowed >-- gaSolutionSpace :: [a] -> [a] >>gaSolutionSpace x = x : gaSolutionSpace (evolvepopulation x) -Stop deceiving yourself until it's too late. -Why did you comment out the type annotation? *Sheepish Grin* its historical, my original thought and attempt was that you would recieve a list of populations and evolve it to a bigger list of populations. Hence the [a] -> [a]. It didnt work out too well as this is what I came up with: gaSolSpace [x:xs] = gaSolutionSpace [x : evolePopulation x] Eventually i realised that I needed to evolve a single population, not a list, which let to a -> [a] and thanks to Keith I now have this: gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom = iterate evolvePopulation Thanks _________________________________________________________________ Add photos to your e-mail with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail ------------------------------ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe End of Haskell-Cafe Digest, Vol 11, Issue 3 ******************************************* _________________________________________________________________ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail

1 0

Re: [Haskell-cafe] Newbie questions
by Crypt Master 03 Jul '04

03 Jul '04

Hi Very very helpful, thanks. I wasnt sure about the "From" on the end, but I get the subtle change in way you see it. Much better than mine. Using you other advice I got: gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom p = iterate evolvePopulation p and even managed to curry it :-) : gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom = iterate evolvePopulation Thanks again. -------------- Kieth: [Snip] I think you mean: gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom x = x : gaSolutionSpaceFrom (evolvepopulation x) gaSolutionSpace = gaSolutionSpaceFrom createRandomPopulation Note that "a" above should be replaced with your population type. Also note the "iterate" function in the standard library does just this. _________________________________________________________________ Tired of spam? Get advanced junk mail protection with MSN 8. http://join.msn.com/?page=features/junkmail

1 0

Re: Newbie questions
by Crypt Master 03 Jul '04

03 Jul '04

>-- gaSolutionSpace :: [a] -> [a] >>gaSolutionSpace x = x : gaSolutionSpace (evolvepopulation x) -Stop deceiving yourself until it's too late. -Why did you comment out the type annotation? *Sheepish Grin* its historical, my original thought and attempt was that you would recieve a list of populations and evolve it to a bigger list of populations. Hence the [a] -> [a]. It didnt work out too well as this is what I came up with: gaSolSpace [x:xs] = gaSolutionSpace [x : evolePopulation x] Eventually i realised that I needed to evolve a single population, not a list, which let to a -> [a] and thanks to Keith I now have this: gaSolutionSpaceFrom :: a -> [a] gaSolutionSpaceFrom = iterate evolvePopulation Thanks _________________________________________________________________ Add photos to your e-mail with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail

1 0

Re: [Haskell-cafe] Newbie questions
by Crypt Master 03 Jul '04

03 Jul '04

[Snip] People say function application in Haskell is written without brackets but this can be misleading, here you do need brackets to indicate that 'gaSolutionSpace [1,2,3,4,5]' is one argument and not two. So you should write: take 5 (gaSolutionSpace [1,2,3,4,5]) [Snip] Thanks alot, this was very helpfull. It also makes more sense now that I looked up the associativity of functions and found it to be left assoc. For some reason I assumed it would automaically bracket form the right as such (take (5 (gaSolutionSpace [1,2,3,4,5]))) but its actually this (((take 5) gaSolutionSpace) [1,2,3,4,5]) Thanks again. _________________________________________________________________ Tired of spam? Get advanced junk mail protection with MSN 8. http://join.msn.com/?page=features/junkmail

1 0

Newbie questions
by Crypt Master 03 Jul '04

03 Jul '04

Hi I consider myself a pretty good imperative programmer, been at it for decades, and am tryibng my hand at Haskell now. Unfrituantly I am not "getting" it all that quickly despite having the multimedia haskell book. To start ghetting some hands on, I thought iI owuld do something which i have done many times before in imperatives, a basic Genetic Algorithm Library. Unfortunatly I am comming unstuck straight away and was hoping some of you kind folk could point in the direction of dry land :-) iIf your not familiar with GAs its not too important, simply a GA searches over the whole solution space randomly. Well not quiet, its a guided search, its guided by evolution ie by the fitness of each indicidual of a random initial population. Evolution is simulated by 3 basic operators, selection, cross over and mutation. selection is which indiviuals get to breed, cross over is how they breed, and mutation is just things intetresting. So after reading the multimedia book, Iimmediately thought of a defining the solution space as a infinite list. I was hoping then I could do things like take 5 gaSolutionSpace to get 5 iterations or generations. My first attempt tied to use lis syntax [], but it wouldnt compile and after seeing "numsFrom" ina tutorial I redefined it as such. Here is what I have so far: -- gaSolutionSpace :: [a] -> [a] -- gaSolutionSpace [] = gaSolutionSpace createRandomPopulation -- recursive base case gaSolutionSpace x = x : gaSolutionSpace (evolvepopulation x) evolvepopulation :: a -> a evolvepopulation p = mutate cross select p -- createRandomPopulation :: [Num a] createRandomPopulation = [1,23,4,5,6] cross p = p mutate p = p select p = p ---- The take operator doesnt work on this. from hugs: HAGA> take 5 gaSolutionSpace [1,2,3,4,5] ERROR - Type error in application *** Expression : take 5 gaSolutionSpace [1,2,3,4,5] *** Term : take *** Type : Int -> [e] -> [e] *** Does not match : a -> b -> c -> d I am not sure I follow this. I assume its cause I didnt use the list notation in definaing gaSolutionSpace. Any ideas on how to do that. ? What about using map. It occurs to me that you can define gaSolutionspace as a map of the evolvolepopuloation function acrossan infinite solution space, but I dont know how to makethis infinte list to map over ...? There ar 2 papaers on GAs in haskell, but they use monads. I realise for performance I will probably have to use them too, but for now I would liek to do it without mondas even if performance isnt optimal. Sorry again for the newbie questions, but any help is appreciated. Stephen _________________________________________________________________ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail

5 4

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