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
On Thu, 2004-07-01 at 17:01, Crypt Master wrote:
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.
[snip]
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
What this error message is telling you is this: * The 'take' function wants two parameters, an Int and a list of some type '[e]'. It will give you back a list of the same type * You have given it three parameters, or to put it another way you are using 'take' as if it had type 'a -> b -> c -> d' (for some a,b,c & d) The solution then is to just pass two arguments. How do you do that? In what you've written can you see that you're passing 3 arguments? take 5 gaSolutionSpace [1,2,3,4,5] 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]) Now there are just two parameters, where the second parameter is another expression rather than a simple variable or constant. If your gaSolutionSpace takes a list type and returns a list type then this will be well typed, and hugs will not complain. Duncan
-- gaSolutionSpace :: [a] -> [a] -- gaSolutionSpace [] = gaSolutionSpace createRandomPopulation -- recursive base case gaSolutionSpace x = x : gaSolutionSpace (evolvepopulation x)
This isn't quite right - you don't want the *last* element to be the initial population, but the first.
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.
--KW 8-)
--
Keith Wansbrough
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
Crypt Master writes: pretty much requires it to be an identity function, because it's not allowed to make any assumptions about the values it takes. 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]
Then you want
evolve :: Population -> Population
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. 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
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.
gaSolutionSpace :: Population -> [Population] gaSolutionSpace p = p : gaSolutionSpace (evolve p)
-- alternative: -- gaSolutionSpace = iterate evolve
Note that the type you want is Population -> [Population]. Now, we get to the problem. You were trying take 5 gaSolutionSpace [1,2,3,4,5] But take :: Int -> [a] -> [a]. That means the second argument has to be a list, not a function which produces a list. But that's easily solved by some parentheses: take 5 (gaSolutionSpace [1,2,3,4,5]) Or you can define another function:
generate :: Int -> Population -> [Population] generate n p = take n (gaSolutionSpace p)
-- alternative: -- generate n = take n . gaSolutionSpace
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.
--
David Menendez
participants (5)
-
Crypt Master -
David Menendez -
Duncan Coutts -
Ferenc Wagner -
Keith Wansbrough