January 2011 - Haskell-Cafe

companies using Haskell or other FP languages near Rochester?
by Edward Amsden 31 Jan '11

31 Jan '11

I'm an undergraduate CS student (4th year status) looking for an co-op or internship in the Rochester area. I'd really like to do something with functional programming or Haskell specifically, but I'm not sure if anyone in this area does that. Staying near Rochester is important because I'd also like to take one or two classes at my school (Rochester Institute of Technology) over the summer. Any ideas? -- Edward Amsden Undergraduate Computer Science Rochester Institute of Technology www.edwardamsden.com

1 0

Haskell WalkSat algorithm implementation
by Manolache Andrei-Ionut 31 Jan '11

31 Jan '11

I need some help if possible with the following problem.....The WalkSat algorithm takes a formula, a probability 0 =< p =< 1, and a boundary of maximum flips maxflips and returns a model that satisfies the formula or failure. The algorithm begins by assigning truth values to the atoms randomly, ie. generating a random model. Then it proceeds to flip the value of an atom from one of the unsatisfied clauses until it is able to find a model that satisfies the formula or reaches the maximum number of flips. In order to select which atom from the currently selected clause to flip, it follows two strategies: 1. Either flip any atom randomly. 2. Or flip the atom that maximizes the number of satisfied clauses in the formula. The choice to flip randomly is followed with probability p. 1.atomsClause :: Clause ! [Atom] This function must take a Clause and return the set of Atoms of that Clause. Note that the set should not contain any duplicates. 2. atoms :: Formula![Atom] This function must take a Formula return the set of Atoms of a Formula. Note that the set should not contain any duplicates. 3. isLiteral :: Literal ! Clause ! Bool This function returns True if the given Literal can be found within the Clause. 4. flipSymbol :: Model ! Atom ! Model This function must take a Model and an Atom and flip the truth value of the atom in the model. Now I've done the first 3 I need some help with the last one, Here is the code: module Algorithm where import System.Random import Data.Maybe import Data.List type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] type Formula = [Clause] type Model = [(Atom, Bool)] type Node = (Formula, ([Atom], Model)) atomsClause :: Clause -> [Atom] atomsClause = nub . map snd atoms :: Formula -> [Atom] atoms =atomsClause . concat isLiteral :: Literal -> Clause -> Bool isLiteral (b,a) cs = or[x==b && y==a|(x,y)<-cs] flipSymbol :: Model -> Atom -> Model flipSymbol = undefined ---the last one Thank you.

3 2

Typing problem
by michael rice 31 Jan '11

31 Jan '11

I'm mapping a function over a list of data, where the mapping function is determined from the data. g f l = map (g l) l So g serialize "prolog" -> [4,5,3,2,3,1] But I'm having typing problems trying to do a similar thing with a function that statistically normalizes data. See: http://people.revoledu.com/kardi/tutorial/Similarity/Normalization.html#Sta… So g normalize [2,5,3,2] -> [-0.7071067811865475,1.414213562373095,0.0,-0.7071067811865475] Is my typing for normalize too loose. Should I be using Floating rather than Num? Michael =======Code============== {- See Problem 42, pg. 63, Prolog by Example, Coelho & Cotta Generate a list of serial numbers for the items of a given list, the members of which are to be numbered in alphabetical order. *Main> serialize "prolog" [4,5,3,2,3,1] *Main> serialize "int.artificial" [5,7,9,1,2,8,9,5,4,5,3,5,2,6] *Main> ["prolog"] >>= serialize [4,5,3,2,3,1] *Main> ["int.artificial"] >>= serialize [5,7,9,1,2,8,9,5,4,5,3,5,2,6] -} import Data.Map hiding (map) import Data.List {- serialize :: [Char] -> [Int] serialize l = map (f l) l where f = ((!) . fromList . ((flip zip) [1..]) . (sort . nub)) -} serialize :: (Ord a, Integral b) => [a] -> a -> b serialize = ((!) . fromList . ((flip zip) [1..]) . (sort . nub)) g f l = map (f l) l normalize :: (Num a, Num b) => [a] -> a -> b normalize l = let (total,len) = sumlen l avg = total/len stdev = sqrt $ ((/) (len-1)) $ sum $ map ((** 2.0) . (subtract avg)) l in ((/) stdev) . (subtract avg) sumlen :: (Num a, Integral b) => [a] -> (a,b) sumlen l = sumlen' l 0 0 where sumlen' [] sum len = (sum,len) sumlen' (h:t) sum len = sumlen' t (sum+h) (len+1) ========================= Prelude> :r [1 of 1] Compiling Main ( serialize2.hs, interpreted ) serialize2.hs:34:32: Could not deduce (Integral a) from the context (Num a, Num b) arising from a use of `sumlen' at serialize2.hs:34:32-39 Possible fix: add (Integral a) to the context of the type signature for `normalize' In the expression: sumlen l In a pattern binding: (total, len) = sumlen l In the expression: let (total, len) = sumlen l avg = total / len stdev = sqrt $ ((/) (len - 1)) $ sum $ map ((** 2.0) . (subtract avg)) l in (/ stdev) . (subtract avg) serialize2.hs:36:61: Could not deduce (Floating a) from the context (Num a, Num b) arising from a use of `**' at serialize2.hs:36:61-66 Possible fix: add (Floating a) to the context of the type signature for `normalize' In the first argument of `(.)', namely `(** 2.0)' In the first argument of `map', namely `((** 2.0) . (subtract avg))' In the second argument of `($)', namely `map ((** 2.0) . (subtract avg)) l' serialize2.hs:37:18: Couldn't match expected type `b' against inferred type `a' `b' is a rigid type variable bound by the type signature for `normalize' at serialize2.hs:33:25 `a' is a rigid type variable bound by the type signature for `normalize' at serialize2.hs:33:18 In the expression: (/ stdev) . (subtract avg) In the expression: let (total, len) = sumlen l avg = total / len stdev = sqrt $ ((/) (len - 1)) $ sum $ map ((** 2.0) . (subtract avg)) l in (/ stdev) . (subtract avg) In the definition of `normalize': normalize l = let (total, len) = sumlen l avg = total / len .... in (/ stdev) . (subtract avg) Failed, modules loaded: none.

3 3

A few days to go before the old server goes down
by Henk-Jan van Tuyl 31 Jan '11

31 Jan '11

7 8

The implementation of Control.Exception.bracket
by Leon Smith 31 Jan '11

31 Jan '11

There is a common idiom used in Control.Concurrent libraries, as embodied in the implementation of bracket: http://www.haskell.org/ghc/docs/7.0-latest/html/libraries/base-4.3.0.0/src/… bracket before after thing = mask $ \restore -> do a <- before r <- restore (thing a) `onException` after a _ <- after a return r Is there any particular reason why bracket is not implemented as: bracket before after thing = mask $ \restore -> do a <- before r <- restore (thing a) `finally` after a return r Is there some subtle semantic difference? Is there a performance difference? It seems like a trivial thing, but I am genuinely curious. Best, Leon

2 1

Re: [Haskell-cafe] ANNOUNCE: genprog-0.1
by Jan Snajder 31 Jan '11

31 Jan '11

(Moved from haskell(a)haskell.org) Hi Kenneth, I'm sorry for the very late reply. On Wed, 2010-12-08 at 10:01 +0100, Kenneth Hoste wrote: > Hi Jan, > > On 11/29/2010 12:55 PM, Jan Snajder wrote: > > Dear Haskellers, > > > > I am pleased to announce the release of genprog-0.1, a genetic > > programming library. > > > > (snip) > > Very interesting, and nice job on the code (elegant, well-structured, > well-documented, ...)! Thank you. This was my first shot at building a Haskell library and I'm flattered to receive such positive comments :-) > Genetic programming recently got my attention because one of the bots in > the Google AI contest was built using this technique (see > http://ai-contest.com/forums/viewtopic.php?f=17&t=1136) and it > performed really well (way better than my hand-crafted bot). Interesting, thanks for the link. > I have a bit of experience with genetic algorithms, on a practical and > pragmatic level. The field of genetic programming is something I hope to > look at and play with in the upcoming months (just for fun). > > I was kind of planning to implement my own genetic programming library > in Haskell as I became familiar with the field, but after diving into > your code it quickly became clear to me you've done a way better job > than I would have. > > I really like the example you provided for evolving an expression that > computes a specified integer value. I kept this example deliberatly simple so to make it clear how you can use the library. The example is actually a degenerated case of symbolic regression, in which you are given only a single instance to train at, rather than a set of instances. You can find much more interesting examples in Koza's book. > I plan to start playing with that > and improve the example (faster convergence to a perfect solution, and > also tweaking the current GP config to obtain smaller solutions). > > > A couple of questions (some fairly unrelated to Haskell): > > How hard would it be to extend the current version to support the > evolution of actual Haskell programs? As far as I can tell, the current > version has support for (simple?) self-defined expressions, but this > seems like a long way from supporting Haskell programs with > multi-argument functions that operate on lists, etc., even if you just > limit it to non-monadic Haskell98 code. Actually, I have no idea. :-) I don't know if there is a data structure that can represent an AST of a Haskell program. I guess there is, because I guess at some point a compiler like GHC has to maintain such a structure internally, but I never looked into this. At present, I am more than satisfied to be able to evolve custom-made data structures. Another issue with evolving arbitrary Haskell (or whatever) programs is the "closure property". When doing crossover, you have to ensure that what you get by exchanging two subtrees still is a valid program. In other words, if F is a set of (arbitrary arity) functional nodes and T is a set of terminal nodes, then, given a functional node F(x1,...,xi,...xn), you should be able to substitute for argument xi each element of F `union` T. Obviouslly, this will not work for programms in general and you would have to either introduce specialized crossover operations or treat the nodes differently depending on their types. In genprog, I have kept things simple and closure propery is ensured by allowing crossover to take place only at nodes that are of the same type as the root node. This is certainly a limitation, but still I think one can do interesting stuff with it. > > Have you considered playing with dynamic values for the various > parameters that steer the evolution, i.e. population size, > crossover/mutation probabilities, etc.? > One thing I've always wanted to try (but never really got to it) is e.g. > increasing the mutation probability as the evolution seems to be getting > stuck in a (local?) optimum. Also, shrinking the population size if > enough progress is being made could be interesting, to speed up the > evolutionary process. Are you aware of studies that do such a thing? Yes, definitely! Variable mutation probability is often used in genetic algorithms to improve the results. The idea is to have higher mutation probability in the beginning, so to encourage exploration, and then decrease the mutation probability as the evolution progresses, so to encourage exploitation. This increases the chances of not getting stuck in a local optima. But I didn't include this into genprog because I don't need variable mutation right now. I will probably do it in the next release. The most straightforward to do it, I guess, would be make the mutation prob. (and pop. size) a function of the evolution state. There are also other things that I plan to include in the next release. I hope I will find time to do it. Btw., mutation is actually rarely used in GP (unlike in GA). Koza, for example, used mutation in one example only. The thing is that, if you think of mutation as a replacement of a subexpression with a randomly generated subexpression, then you already can do this with crossover. Now, this only true for this default type of mutation. If you have a custom-defined mutation operator, one that changes a node depending on its value and/or type, than this cannot be accomplished by crossover anymore. Whether or not you need custom-defined mutations depends on the task at hand. E.g., if the expressions you're evolving feature values from a very large domain set, than a crossover operation alone will not get you enough genetic diversity. For this reason I've defined in genprog the mutation operation as a function of an expression that is being mutated. > Are you planning to actively maintain and extend this library? Are you > using it for research purposes, or did you hack this together just for > fun (if so, nice job!). What do you plan to use it for? Yes, I will maintain the library actively. I did this for fun, of course :-), and also for research, which I also do for fun :-) I am using the library for solving specific problems related to natural language processing. > Anyway, great job, I hope I'll find the time to play around with this. So do I. Please let me know if you have any suggestions on how to improve the library. If you do interesting stuff with it, please let us know what it is. Cheers, Jan

2 1

Instantiation problem
by Patrick Browne 31 Jan '11

31 Jan '11

Below is some code that is produces information about the *types* used for measuring (e.g. metres). The following evaluation returns 1.00 which the convert factor for metres. convertFactorToBaseUnit (unit (LengthInMetres 7)) . The next evaluation returns the type, Metre, of data being measured unit (LengthInMetres 7) Using the particular definitions below is it possible to make an instance of MetricDescription for centimetres? I have an error on the defintion of the unit function in the definition of the MetricDescription instance. As far as possible I would like to retain the data types and class structures. Thanks, Pat class (Unit unit) => MetricDescription description unit | description -> unit where unit :: description -> unit valueInUnit :: description -> Double valueInBaseUnit :: description -> Double valueInBaseUnit d = (convertFactorToBaseUnit(unit d)) * (valueInUnit d) data Metre = Metre deriving Show data Centimetre = Centimetre deriving Show -- Each member of the Unit class has one operator convertFactorToBaseUnit -- that takes a measurement unit (say metre) and returns a conversion factor for that unit of measurement class Unit unit where convertFactorToBaseUnit :: unit -> Double -- An instance for metres, where the convert factor is 1.0 instance Unit Metre where convertFactorToBaseUnit Metre = 1.0 -- An instance for metres, where the convert factor is 0.1 instance Unit Centimetre where convertFactorToBaseUnit Centimetre = 0.1 data LengthInMetres = LengthInMetres Double deriving Show data LengthInCentimetres = LengthInCentimetres Double deriving Show -- This seems fine instance MetricDescription LengthInMetres Metre where valueInUnit (LengthInMetres d) = d unit l = Metre -- This is the instance that I cannot get to work -- The unit 2 function seems to be the problem. -- instance MetricDescription LengthInCentimetres Centimetre where -- valueInUnit (LengthInCentimetres d) = d -- unit 2 = Centimetre This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

4 8

Re: [Haskell-cafe] Code from Haskell School of Expression hanging.
by michael rice 30 Jan '11

30 Jan '11

The sample program (the "active" version) here runs fine, so the OpenGL GLFW must have been installed properly. Must be the SOE stuff causing the problem. http://www.haskell.org/haskellwiki/GLFW Michael --- On Sat, 1/29/11, Daniel Fischer <daniel.is.fischer(a)googlemail.com> wrote: From: Daniel Fischer <daniel.is.fischer(a)googlemail.com> Subject: Re: [Haskell-cafe] Code from Haskell School of Expression hanging. To: "michael rice" <nowgate(a)yahoo.com> Date: Saturday, January 29, 2011, 9:37 PM On Sunday 30 January 2011 03:27:55, michael rice wrote: > I'm using the OpenGL stuff (GLFW). Same set of problems? No idea, I haven't used a graphics library for a long time.

3 14

Re: [Haskell-cafe] [Haskell] ANNOUNCE: jhc 0.7.7 is out.
by Roman Cheplyaka 30 Jan '11

30 Jan '11

Greetings! A few questions about the inclusion of parsec: 1. It is parsec-2, not parsec-3, right? 2. Does this change consist of merely inclusion parsec as a standard library, or are there any compiler improvements in this release that made it possible to build parsec? * John Meacham <john(a)repetae.net> [2011-01-29 20:47:20-0800] > Announcing jhc 0.7.7! This release fixes a large number of bugs that cropped up > when compiling haskell out in the wild as well as adds some more features. A > major one being the garbage collector is enabled by default. > > http://repetae.net/computer/jhc/ > > Changes: (including some changes from the unannounced 0.7.6 release) > > * The Garbage Collector is now enabled by default. > * new standard libraries > * transformers > * parsec > * QuickCheck > * report proper errors with line numbers for various issues with compiled code. > * New option '-C' that compiles to C code and stops, useful for targeting other > platforms or building shared libraries. > * Nintendo Wii added as target (thanks to Korcan Hussein) > * Fix major performance bug that kept WRAPPERs from being inlined in > certain places. > * Typechecking speed greatly increased. > * monomorphism-restriction flag is now respected > * empty class contexts now work > * unicode in haskell source supported now > * Type Defaulting now works properly > * RULES parse like ghc now for compatibility > * 'do' 'where' on same indent now parses > * Build system fixes and cleanups > * irrefutable lambda pattern bindings desugar properly now. > * GHC parsing regression tests have been ported to jhc, helped find > and fix many bugs. > * Certain optimizations would discard RULES, these have been fixed. > * Removed quadratic behavior in optimizer, speeds things up noticibly. > * Garbage collector improvements, caches are pre-initialized. > * Fix shiftL/R implementations for built in types. > * All Num, Real, and Integral magic removed from compiler. This is a very > good thing. > * improved help messages > > John > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell -- Roman I. Cheplyaka :: http://ro-che.info/ Don't worry what people think, they don't do it very often.

2 1

Code from Haskell School of Expression hanging.
by jean legrand 30 Jan '11

30 Jan '11

Maybe you could try The HGL package http://hackage.haskell.org/package/HGL and then replace import SOE by import Graphics.SOE.

1 0