September 2007 - Haskell-Cafe

let and fixed point operator
by Peter Hercek 06 Sep '07

06 Sep '07

Hi, I find the feature that the construct "let x = f x in expr" assigns fixed point of f to x annoying. The reason is that I can not simply chain mofifications a variable like e.g. this: f x = let x = x * scale in let x = x + transform in g x When one is lucky then it results in a compile error; in worse cases it results in stack overflow in runtime. The annoying part is figuring out new and new variable names for essentially the same thing to avoid the search/evaluation of the fixed point. I suppose Haskell was designed so that it makes sense. The only usage I can see is like this: let fact = \x -> if x == 0 then 1 else x * fact (x-1) in ... but that is not any shorter than: let fact x = if x == 0 then 1 else x * fact (x-1) in So the question is what am I missing? Any nice use cases where fixed point search is so good that it is worth the trouble with figuring out new and new variable names for essentially the same stuff? Peter.

30 66

Re: [Haskell] (no subject)
by Scott Williams 06 Sep '07

06 Sep '07

[bcc haskell, cc haskell-cafe] On 9/5/07, Tomi Owens <t.owens(a)hautlieu.sch.je> wrote: > > Hi there. I'm a teacher of Maths and am working my way through the Euler > Project problems for fun. I have mostly been using Basic, but have read up > about Haskell and think it looks like a sensible way to solve many of the > problems. > > OK, so I've downloaded GHCi and am trying to teach myself. > > So far I have done this: > > ___ ___ _ > / _ \ /\ /\/ __(_) > / /_\// /_/ / / | | GHC Interactive, version 6.6.1, for Haskell 98. > / /_\\/ __ / /___| | http://www.haskell.org/ghc/ > \____/\/ /_/\____/|_| Type :? for help. > > Loading package base ... linking ... done. > Prelude> let f (a,b) = a * floor (100000/b) > Prelude> f(2,5) > 40000 Here you can find out type ghci has inferred for this function. > :t f f :: (RealFrac b, Integral b1) => (b1, b) -> b1 This function works just as I want it to. > > Now I try creating a list: > > Prelude> [(a2+b2,a)| a <- [1..4] , b<- [1..4], a2+b2<20, b<=a] > [(2,1),(5,2),(8,2),(10,3),(13,3),(18,3),(17,4)] Let's assign this to an intermediate variable so we can query it's type: Prelude> let lst = [(a ^ 2 + b ^ 2, a) | a <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> lst [(2,1),(5,2),(8,2),(10,3),(13,3),(18,3),(17,4)] Prelude> :t lst lst :: [(Integer, Integer)] aha; here's the source of the type mismatch: Prelude> :t floor floor :: (RealFrac a, Integral b) => a -> b Floor has to take a RealFrac. According to hoogle[1], we can use various floating-point approximations (Float, Double, CFloat, etc) or we can use the exact Rational type. [1] http://haskell.org/hoogle/?q=RealFrac You can get your types to match by declaring your list to be of type [(Rational, Rational)] either by explicitly typing one of the untyped variables or the entire expression: Prelude> let lst = [(a ^ 2 + b ^ 2, a) | (a::Rational) <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> :t lst lst :: [(Rational, Rational)] Prelude> let lst :: [(Rational, Rational)] = [(a ^ 2 + b ^ 2, a) | a <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> :t lst lst :: [(Rational, Rational)] and this works > So now I try to apply the function to the list: > > Prelude> map (f) [(a2+b2,a)| a <- [1..4] , b<- [1..4], a2+b2<20, b<=a] > > and I get this result: > > <interactive>:1:5: > Ambiguous type variable `t' in the constraints: > `Integral t' arising from use of `f' at <interactive>:1:5 > `RealFrac t' arising from use of `f' at <interactive>:1:5 > Probable fix: add a type signature that fixes these type variable(s) I'm sorry, but I don't quite get how to set the type signature and how it > will apply to my function... > > Thanks, Hope this helps Tomi > -------------------------------------------------------------------------------- > > > Department for Education, Sport and Culture E Mail > This message is for the named person's use only. It may contain > confidential, proprietary or legally privileged information. No > confidentiality or privilege is waived or lost by any mistransmission. > If you receive this message in error, please immediately delete it and all > copies of it from your system, destroy any hard copies of it and notify the > sender. You must not, directly or indirectly, use, disclose, distribute, > print, or copy any part of this message if you are not the intended > recipient. The Department for Education, Sport and Culture and any of its > establishments each reserve the right to monitor all e-mail communications > through its networks. > > Any views expressed in this message are those of the individual sender, > except where the message states otherwise and the sender is authorised to > state them to be the views of any such entity. > > The Department for Education, Sport and Culture shall not be liable to > the recipient or any third party for any loss or damage, however it appears, > from this e-mail or its content. This includes loss or damage caused by > viruses. It is the responsibility of the recipient to ensure that the > opening of this message and its attachments shall not adversely affect > systems or data. > > > -------------------------------------------------------------------------------- > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > -- Scott Williams

3 3

Code from "Why Functional Programming Matters"
by Andrew Wagner 05 Sep '07

05 Sep '07

I've been reading the classic "Why functional programming matters" paper [1] lately, particularly looking at the alpha beta stuff. I've ported all his code to haskell, but I have a question. His algorithm takes a board position, creates a gametree out of it, maps a static evaluation function over the gametree, then uses alpha beta to find the real evaluation from a Tree Int. But of course, in an actual application, what you actually want is the best MOVE from the current position (or, even more ideally, the so-called "principal variation", which is the best series of moves from the current position). Is there a good way to collect this, without mapping some sort of function over the tree that puts a list of moves on every node too? Hughes seems to completely ignore this, and I wonder if it's because it gets ugly to implement.

9 12

Re: [Haskell-cafe] Re: [Off topic] Proving an impossibility
by Miguel Mitrofanov 05 Sep '07

05 Sep '07

> It depends on arbitrary restrictions on what constitutes an > (boolean) expression, something that is anathema to > functional programmers :-) Spot the language: > while if E > then S; F > else False > fi > do T > od > > It reminds me of a paper by Knuth, where he states that > > "goto" statement is necessary; don't remember the title, > > however. > I don't remember needing a goto in Haskell... Well, for imperative languages, of course.

6 7

[Off topic] Proving an impossibility
by Vimal 05 Sep '07

05 Sep '07

Hi In my Paradigms of Programming course, my professor presents this piece of code: while E do S if F then break end T end He then asked us to *prove* that the above programming fragment cannot be implemented just using if and while statement, even if S and T can be duplicated a finite number of times He also asked us to state our assumptions if any. 1. We have assignment statements (to create a flag and check) 2. The execution of E or F does not affect execution of S or T... Well, learning Haskell, I quickly realized that even if S and T have to be expressions and came up with this, assuming that 1. There are boolean operations 2. Boolean expressions are evaluated from Left to Right 3. Boolean expressions can be short-circuited while E and (S or 1) and F and (T or 1) do (* Nothing *) end But I would also like to consider an option of proving that its impossible, under the given constraints... Any thoughts? Vimal

4 3

ANN: Finance-Quote-Yahoo 0.3
by brad clawsie 05 Sep '07

05 Sep '07

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Finance-Quote-Ya… i know minor point releases do not merit a list announcement but yahoo discontinued a url i was using to download data, so users of this package must upgrade. sorry for the hassle. thanks brad

1 0

Request for code review - Knuth Morris Pratt for Data.Sequence
by Justin Bailey 04 Sep '07

04 Sep '07

Using the code developed for ByteStrings by myself, Christ Kuklewicz and Daniel Fischer, I've implemented Knuth-Morris-Pratt substring searching on Data.Sequence "Seq" values. Attached you'll find the library in kmp.zip.safe. The algorithm is implemented in the module Data.Sequence.KMP. At the root, SpeedTest.hs can be compiled on Windows with the "prof_compile.bat" file included (you'll need to install the "regex-dfa" and "regex-base" packages from Hackage to build). SpeedTest searches for a known value in the 7 MB file "endo.dna" (which can be downloaded from http://www.icfpcontest.org/endo.zip) using several different algorithms and methods: strict and lazy bytestrings, regular expressions, and the KMP algorithm for "Seq" values. SpeedTest is pretty fast but I worry about its space usage. It may just be the nature of Seq values, but I cannot get it to run in constant space when I think it should be. I'm especially interested in help here. All comments and feedback are welcome. Since the zip file includes a darcs context file, feel free to send patches. Justin

1 0

FFI and DLLs
by Lewis-Sandy, Darrell 04 Sep '07

04 Sep '07

An early proposal for the FFI supported importing functions directly from dynamic link libraries: www. <http://www.haskell.org/hdirect/ffi-a4.ps.gz> haskell.org/hdirect/ffi-a4.ps.gz This looks like it was dropped from the final version of the addendum in favor of C header files as the sole form of import entities. Not being a C programmer, how would one go about importing a foreign function (e.g. void Foo(void) ) from a dynamic link library (e.g. foo.dll)?? Would someone be willing to provide an explicit example?

2 1

Re: [Haskell-cafe] [Off topic] Proving an impossibility
by Miguel 04 Sep '07

04 Sep '07

>On 9/3/07,Vimal<j.vimal(a)gmail.com> wrote: >>while E do >>S >>if F then >>break >>end >>T >>end >> >>He then asked us to *prove* that the above programming fragment cannot >> >>be implemented just using if and while statement, even if S and T can >>be duplicated a finite number of times >But it IS possible. Just add a boolean flag: Possibly, you are not allowed to change the sequence of machine operations at all. See, if you change "while(A){B}" to "if(A){B};while(A){B}", the sequence is exactly the same; but it's not possible in this case. It reminds me of a paper by Knuth, where he states that "goto" statement is necessary; don't remember the title, however.

2 1

Are type synonym families really equivalent to fundeps?
by Chris Smith 04 Sep '07

04 Sep '07

The following code builds and appears to work great (assuming one allows undecidable instances). I have tried both a natural translation into type synonym families, and also the mechanical transformation in http://www.cse.unsw.edu.au/~chak/papers/tyfuns.pdf -- but I can't get either to work. The two fishy things are: 1. There is a functional dependency (a -> t) in the original. Actually, this isn't always true since t is sometimes not uniquely determined by a; but GHC always seems to do the right thing anyway. There doesn't seem to be any way to "cheat" like this with type families. 2. In the second and fourth instances, the type variable x appears twice in the parameters of the type function built from the fundep (a b -> c). This causes an error. If I try adding (x ~ x') to the context and making one of them x' instead of x, I get different errors. I'm starting to this this is an example of using functional dependencies that has no translation to type families. Can anyone free me of such thoughts? Code with fundeps is: data Var a = Var Int (Maybe String) data RHS a b = RHS a b class Action t a b c | a -> t, a b -> c, a c -> b instance Action t () y y instance Action t (Var x) (x -> y) y instance Action t [t] y y instance (Action t a b c) => Action t (RHS (Var x) a) (x -> b) c instance (Action t a b c) => Action t (RHS [t] a) b c -- Chris Smith

4 7