- Haskell-Cafe - Haskell.org

Implementation of the Floyd-Warshall algorithm
by frederic＠ka-ge-ro.org 28 Jul '06

28 Jul '06

Hi, I'm new to Haskell (yet I am very familiar with Lisp and OCaml), and I am trying to implement the Floyd-Warshall algorithm (finding the minimal distance between two nodes in a weighted graph). For an input graph with 101 nodes, the obvious C version takes 0.01 s on my machine. My first totally functional implementation in Haskell took 6s... for a graph with 10 edges. (This version considered that a graph is given as its adjacency matrix, which is represented as a 2-uple in ([k], k -> k -> Double)). [I do not show my code, as I am ashamed of it :-S] My first question is: what would an (efficient?) version of the algorithm using this representation would look like ? Is it possible to do without ressorting to the ST monad ? Now, I have been trying to implement it in a more imperative way, to understand how the ST monad works. It runs in 0.6s for a 101-noded graph, which is much, much faster than the original version but still much slower than the C version. I would be very grateful if someone cared to explain why this is unefficient and how to make it faster (Without using the FFI :-|) Thanks by advance. (BTW, I'm using the ghc-6.42 compiler with -O2 flag). -- Frederic Beal -- Code begins here module FW (bench) where import Control.Monad import Control.Monad.ST import Data.Array.ST update :: STUArray s (Int, Int) Double -> Int -> Int -> Int -> ST s () update arr i j k = do aij <- readArray arr (i, j) ajk <- readArray arr (j, k) aik <- readArray arr (i, k) if aij + ajk < aik then do writeArray arr (i, k) (aij + ajk) else return () updateLine arr i j n = do mapM_ (update arr i j) [0..n] updateRow arr i n = do mapM_ (\x -> updateLine arr i x n) [0..n] updateStep arr n = do mapM_ (\x -> updateRow arr x n) [0..n] -- The actual FW invocation canonicalize = updateStep -- From here on, the "testing" suite count = 100 -- A test array: M[i, j] = 1 + ((x+y) mod count) orgArray :: ST s (STUArray s (Int, Int) Double) orgArray = do v <- newArray ((0, 0), (count, count)) 0.0 mapM_ (\x -> mapM_ (\y -> writeArray v (x, y) ((1+) $ fromIntegral (mod (x+y) count))) [0..count]) [0..count] return v sumDiag :: STUArray s (Int, Int) Double -> Int -> ST s Double sumDiag arr n = do foldM (\y x -> do a <- readArray arr (x, x) return $ a + y) 0.0 [0..n] orgDiag = do arr <- orgArray v <- sumDiag arr count return v cptDiag = do arr <- orgArray canonicalize arr count v <- sumDiag arr count return v bench = do val <- stToIO cptDiag diag <- stToIO orgDiag print val print diag

5 5

if-then-else as rebindable syntax (was Re: Why does Haskell have the if-then-else syntax?)
by Niklas Broberg 28 Jul '06

28 Jul '06

I would be happy to write up a trac-ticket for this - I could even try to implement it in GHC. However, I'm surprised that you agree with it so easily since it breaks some Haskell 98-ish stuff in un-nice ways. :-) First of all, programs that import names from the Prelude explicitly would no longer be able to use if-then-else unless they also added 'cond' to that input list (or redefined it of course). This shouldn't really be a problem, since the rebindable syntax is turned on by adding some flag anyway, and if you add that flag you know you're no longer H98. Still, it's going to break a lot of existing programs. The second problem is that it would require the addition of the cond function to the Prelude. This will probably not break too many existing programs, but still it is a more serious problem since it will have effect even without any flags to GHC. Or is it possible to govern the contents of the Prelude based on flags? I would really like to see this implemented, and I don't think the above is serious enough that we shouldn't. There may be some that don't agree though. Speak up now, or forever hold your peace! Also, is cond the best name for the suggested function? If we don't expect anyone to really use it without the sugar, we could name it whatever weird thing so as to break as few existing programs as possible. It would make explicit import a bit more akward though. But I suspect that if this function did exist in the Prelude, people would start using it a lot. Does anyone have any better suggestions, or is cond the name of the day? /Niklas On 7/27/06, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > GHC does indeed include the notion of "rebindable syntax". It would be > straightforward to extend it to include if-then-else. In effect, that > would mean that > if e1 then e2 else e3 > would behave exactly like > cond e1 e2 e3 > including from the point of view of typing. (You could choose a > different name than 'cond'.) Then by importing a 'cond' with (say) type > > cond :: MyBool -> b -> b > you could use a different kind of Boolean. You could even overload the > bool: > cond :: Boolean a => a -> b -> b > > This could be done with a few hours work. But not a few minutes. Want > to put a feature request in Trac? > > Simon > > | -----Original Message----- > | From: haskell-cafe-bounces(a)haskell.org > [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Niklas > | Broberg > | Sent: 27 July 2006 09:01 > | To: Haskell-cafe > | Subject: Re: [Haskell-cafe] Why does Haskell have the if-then-else > syntax? > | > | I often find myself at odds with this choice. The reason is that I use > | Haskell as a host for embedded languages, and these often come with > | their own control flows. So I find myself wanting to write my own > | definition of the if-then-else construct that works on terms of some > | other type, e.g. tests on values of type Exp Bool instead of Bool, and > | at the same time make sure that the user doesn't use the built-in > | if-then-else. Sure, I can (and do) call my own version if_, ifElse or > | something else along those lines, but it's sure to be a constant > | source of programmer errors, writing if-then-else instead of if_ by > | habit. > | > | A thought that has crossed my mind on several occasions is, why not > | make the syntactic if-then-else construct rebindable, like the do > | notation? I think I know the answer already -- the do notation is > | syntactic sugar for >>= and company so it's easy to translate it into > | non-prelude-qualified versions of functions with those names. This is > | not the case for if-then-else. But it could be, the prelude could > | define a function if_ (or whatever) that the if-then-else construct is > | made to be sugar for, and thus also amenable to rebinding by not > | prelude-qualifying. > | > | /Niklas > | > | On 7/27/06, Paul Hudak <paul.hudak(a)yale.edu> wrote: > | > Mike Gunter wrote: > | > > | > >I had hoped the "History of Haskell" paper would answer a question > | > >I've pondered for some time: why does Haskell have the if-then-else > | > >syntax? The paper doesn't address this. What's the story? > | > > > | > >thanks, > | > >-m > | > > > | > > > | > Thanks for asking about this -- it probably should be in the paper. > Dan > | > Doel's answer is closest to the truth: > | > > | > I imagine the answer is that having the syntax for it looks > nicer/is > | > clearer. "if a b c" could be more cryptic than "if a then b else > c" > | > for some values of a, b and c. > | > > | > except that there was also the simple desire to conform to > convention > | > here (I don't recall fewer parentheses being a reason for the > choice). > | > In considering the alternative, I remember the function "cond" being > | > proposed instead of "if", in deference to Scheme and to avoid > confusion > | > with people's expectations regarding "if". > | > > | > A related issue is why Haskell does not have a "single arm" > conditional > | > -- i.e. an "if-then" form, which would evaluate to bottom (i.e. > error) > | > if the predicate were false. This was actually discussed, but > rejected > | > as a bad idea for a purely functional language. > | > > | > -Paul > | > > | > _______________________________________________ > | > Haskell-Cafe mailing list > | > Haskell-Cafe(a)haskell.org > | > http://www.haskell.org/mailman/listinfo/haskell-cafe > | > > | _______________________________________________ > | Haskell-Cafe mailing list > | Haskell-Cafe(a)haskell.org > | http://www.haskell.org/mailman/listinfo/haskell-cafe >

12 19

heap issues
by Jeff Polakow 27 Jul '06

27 Jul '06

Hello, Why would ghci run out of heap space (and crash) the second time I run a computation? More specifically, I have a ghci session which goes something like this: *Analysis>run [ ... print out of a very long list ...] *Analysis>run [ ... partial print out GHC's heap exhausted: current limit is 268435456 bytes; Use the `-M<size>' option to increase the total heap size. Shouldn't the garbage collector free up everything in between my top-level function executions? Also, there doesn't appear to be a '-M<size>' flag for ghc (I'm using 6.4.2 on windows xp). thanks, Jeff -- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

3 2

Re: [Haskell-cafe] Why Haskell?
by Matthew Bromberg 27 Jul '06

27 Jul '06

> I used what I thought, initially was an elegant contruction technique in > Haskell. Something like this > do > ... > sequence $ [ reffill b s | s <- [0..(fi temits)-1], b <- [0..(fi nc)-1]] > ...(push list on to matrix stack) Try the sequence_ (note the underscore) function, it should be a big win here. Cheers, Spencer Janssen Now thats interesting. I can see that this function is more appropriate since I do not need to retrieve data from the IO monad, but what I don't understand is why it's actually faster. I will give it a try and test it on a large set to see if things change. Thanks for the tip.

10 11

[FGL] Works on ghc, not on Hugs?
by Stephane Bortzmeyer 27 Jul '06

27 Jul '06

[Warning: beginner with FGL, the Functional Graph Library.] My first program with Data.Graph.Inductive works fine on ghc but raises a type error with hugs, which strikes me as odd. % hugs -98 smalltest.hs __ __ __ __ ____ ___ _________________________________________ || || || || || || ||__ Hugs 98: Based on the Haskell 98 standard ||___|| ||__|| ||__|| __|| Copyright (c) 1994-2005 ||---|| ___|| World Wide Web: http://haskell.org/hugs || || Report bugs to: hugs-bugs(a)haskell.org || || Version: 20050308 _________________________________________ Hugs mode: Restart with command line option +98 for Haskell 98 mode ERROR "smalltest.hs":7 - Type error in application *** Expression : mkGraph mynodes myedges *** Term : myedges *** Type : [(Integer,Integer,[Char])] *** Does not match : [LEdge [Char]] ghc works: % ghc --make smalltest.hs Chasing modules from: smalltest.hs Compiling Main ( smalltest.hs, smalltest.o ) Linking ... % ./a.out 0:"Toto"->[("Couic",1),("Crac",2)] 1:"Tata"->[] 2:"Shadok"->[] 3:"Machin"->[] Here is the code: import Data.Graph.Inductive mynodes = [(0, "Toto"), (1, "Tata"), (2, "Shadok"), (3, "Machin")] myedges = [(0, 1, "Couic"), (0, 2, "Crac")] graph :: Gr String String graph = mkGraph mynodes myedges main = do print graph

1 0

Re: [Haskell-cafe] Why does Haskell have the if-then-else syntax?
by Donn Cave 27 Jul '06

27 Jul '06

Quoth "Sebastian Sylvan" <sylvan(a)student.chalmers.se>: | On 7/27/06, mvanier <mvanier(a)cs.caltech.edu> wrote: | > As opposed to what? | | For example case-of, guards (in combination with let or where), or | just a function: | | if :: Bool -> a -> a -> a | if True t _ = t | if False _ e = e | | -- example usage | myAbs x = if (x < 0) (negate x) x That looks to me like a different way to spell if then else, but maybe that's the answer to the question - conceptually, for every "then" there really is an "else", however you spell it, and only in a procedural language does it make any sense to leave it implicit. The exception that proves the rule is "else return ()" -, e.g., if_ :: Bool -> IO () -> IO () if_ True f = f if_ False _ = return () main = do args <- getArgs if_ (length args > 0) (print args) Strictly speaking that generalizes to any functional context where a generic value can be assigned to the else clause, but there don't tend to be that many other such contexts. Does that answer the question? Donn Cave, donn(a)drizzle.com

3 2

Re: ldap-haskell questions
by Donn Cave 26 Jul '06

26 Jul '06

Quoth Ferenc Wagner <wferi(a)tba.elte.hu>: ... | find -type f | xargs grep -i tls | revealed nothing in my ldap-haskell tree. Isn't your interface | available for the public by chance? It isn't at the moment, and while I don't have anything like a proprietary interest to keep me from posting it somewhere, at the moment I like the idea better of trying to contribute that and maybe one or two other things to this one. I think mine's OK for 300 lines of code, but ldap-haskell has some nice things and is probably a better way forward. The fun contribution will be SASL bind. The TLS option is fairly trivial - I think if you're in a hurry and don't want to wait for it from ldap-haskell, you might be able to hack something up yourself. Now that I look at what I did with ldap_set_option, I recall that s actually a little difficult to assign a type, since the third parameter is sometimes Int, Enum, TimeVal, String, and LDAP_OPT_* values overlap in a way that doesn't really say "enum" to me. So it's reasonably easy to do something, but harder to do it in a way that's generally useful. I'm also unsure of the portability of the things I'd propose to add. I know only the OpenLDAP API, but something about LDAP_OPT_X_TLS hints that it may be non-standard. Donn Cave, donn(a)drizzle.com

2 2

Newbie Q: Deriving MyOrd from Eq problem
by Dmitri O.Kondratiev 26 Jul '06

26 Jul '06

I am trying to derive MyOrd class from Eq (Prelude): class Eq a => MyOrd a where (%<=), (%>), (%>=) :: a -> a -> Bool x %<= y = (x < y || x == y) x %> y = y < x x %>= y = (y < x || x == y) I get these errors: ClassTest.hs:28:21: Could not deduce (Ord a) from the context (MyOrd a) arising from use of `<' at C:/wks/haskell-wks/ClassTest.hs:28:21 Probable fix: add (Ord a) to the class or instance method `%<=' In the first argument of `(||)', namely `x < y' In the definition of `%<=': %<= x y = ((x < y) || (x == y)) In the definition for method `%<=' ClassTest.hs:29:20: Could not deduce (Ord a) from the context (MyOrd a) arising from use of `<' at C:/wks/haskell-wks/ClassTest.hs:29:20 Probable fix: add (Ord a) to the class or instance method `%>' In the definition of `%>': %> x y = y < x In the definition for method `%>' ClassTest.hs:30:21: Could not deduce (Ord a) from the context (MyOrd a) arising from use of `<' at C:/wks/haskell-wks/ClassTest.hs:30:21 Probable fix: add (Ord a) to the class or instance method `%>=' In the first argument of `(||)', namely `y < x' In the definition of `%>=': %>= x y = ((y < x) || (x == y)) In the definition for method `%>=' Failed, modules loaded: none. Q: What's wrong? Why 'Ord' gets into play here? Thanks, Dima

5 7

ghc hackathon start time?
by Greg Fitzgerald 26 Jul '06

26 Jul '06

What time on September 14th will the GHC Hackathon begin? I don't need a precise answer, just a quick one. Plus or minus an hour will do. Thanks, Greg

3 2

Re: [Haskell-cafe] Newbie Q: Deriving MyOrd from Eq problem
by voigt.16734551＠bloglines.com 26 Jul '06

26 Jul '06

Hi Dmitri, I don't have answers for all your questions. But some, at least. --- Dmitri O.Kondratiev" <dokondr(a)gmail.com wrote: > -- Ok, then I can derive MyOrd class directly from Ord: > > class Ord a => MyOrd a where > (%<), (%<=), (%>), (%>=) :: a -> a -> Bool > x %< y = x < y > x %<= y = (x < y || x == y) > x %> y = y < x > x %>= y = (y < x || x == y) > > instance (MyOrd a, MyOrd b) => MyOrd (a,b) where > (x1, y1) %< (x2, y2) = (x1 %< x2) && (y1 %< y2) > (x1, y1) %> (x2, y2) = (x1 %> x2) && (y1 %> y2) > (x1, y1) %<= (x2, y2) = (x1 %<= x2) && (y1 %<= y2) > (x1, y1) %>= (x2, y2) = (x1 %>= x2) && (y1 %>= y2) > > greaterMyOrd :: (MyOrd (a, b)) => (a, b) -> (a, b) -> Bool > greaterMyOrd (x,y) (z,t) = (x,y) %> (z,t) > > -- This should work, right? Yet I get this error message: Only if you tell the compiler to allow constraints of the form (C t), where C is a class and t is not a variable. That's exactly what GHC tells you to try, using -fglasgow-exts. > -- Notwithstanding :) when i comment out declaration: > > -- greaterMyOrd :: (MyOrd (a, b)) => (a, b) -> (a, b) -> Bool > > -- program gets compiled and checking type of 'greaterMyOrd' gives: > > *ClassTest> :t greaterMyOrd > greaterMyOrd :: (MyOrd (a, b)) => (a, b) -> (a, b) -> Bool > > -- which is the same as I tried to declare in the program source. > What is hapenning here? That is indeed a bit funny. Using your instance declaration, GHC could have reduced the constraint "MyOrd (a,b)" to "MyOrd a, MyOrd b". I think there was a discussion on why it does not do so very recently. Maybe you can find it in the archive. > -- Now, when trying to use function 'greaterMyOrd' I get: > > *ClassTest> greaterMyOrd (2, 3) (1, 2) > > <interactive>:1:0: > Ambiguous type variable `a' in the constraints: > `MyOrd a' arising from use of `greaterMyOrd' at <interactive>:1:0-11 > `Num a' arising from the literal `2' at <interactive>:1:14 > Probable fix: add a type signature that fixes these type variable(s) That is because GHC doesn't know which type your literal 2 comes from. So it doesn't know whether there is a MyOrd instance for it, or which to choose. The Num comment comes from GHC only knowing that literal 2 will be of some type in the Num class. But that doesn't tell it anything about possible MyOrd instances. > -- Then I try to declare argument types explicitely and get this: > > *ClassTest> greaterMyOrd (2::MyOrd, 3::MyOrd) (1::MyOrd, 2::MyOrd) > > <interactive>:1:17: > Class `MyOrd' used as a type > In an expression type signature: MyOrd > In the expression: 2 :: MyOrd > In the first argument of `greaterMyOrd', namely `(2 :: MyOrd, 3 :: MyOrd)' > *ClassTest> Well, just as GHC tells you, you should use a type for the signature, not a typeclass. Try something like greaterMyOrd (2::Int, 3::Int) (1::Int,2::Int). Maybe the annotations on the first tuple suffice. > -- I am lost. Please enlight me, what am I doing wrong trying to > create my own class, its instance and then using it. Hope that helped. BTW, you might get problems with overlapping instances. Because with your instance declaration there are two possible ways, for example, to get a MyOrd instance for (Int,Int). The first is via: Ord Int => MyOrd Int => MyOrd (Int,Int) The second is via: Ord Int => Ord (Int,Int) => MyOrd (Int,Int) Ciao, Janis.

1 0