July 2005 - Haskell-Cafe

Re: Coin changing algorithm
by Okasaki, C. DR EECS 14 Jul '05

14 Jul '05

This is a classic dynamic programming problem. Dynamic programming is easy to do in Haskell using recursive arrays. Instead of using recursive arrays directly, however, I'll add a few helper functions that make this kind of problem easier. > import Array > > tabulate :: (Ix a) => (a,a) -> (a -> b) -> Array a b > tabulate bounds f = array bounds [(i,f i) | i <- range bounds] > > dp :: (Ix a) => (a,a) -> ((a->b) -> a -> b) -> a -> b > dp bounds f = (memo!) where > memo = tabulate bounds (f (memo!)) 'tabulate' just turns a function into an array. 'dp' is a memoizing Y combinator. That is, you give the same kind of almost recursive function you would give to the Y combinator, and it "ties the knot" for you, but also interposes an array to hold the intermediate results. (What do I mean by an "almost recursive function"? I mean that instead of writing a recursive function "f = ...f...", you instead write f to take what will end up being the recursive function as its first argument. Then, whenever the f would normally call itself, it instead calls this argument, as in "f rec = ...rec...".) Now, here is the change algorithm, using esentially the same recursion as Radu, except that I introduce an 'i' parameter, that is the index of the largest denomination that you are allowed to use. (Using this parameter makes it easier to store the results in an array than passing around a list of the available coins.) > change m n = dp bounds f (m,n,8) where > bounds = ((0,0,0), (m,n,8)) > coins = listArray (1,8) [1,2,5,10,20,50,100,200] > f rec (m,n,i) > | m == 0 = [[]] > | n == 0 || i == 0 = [] > | c > m = rec (m,n,i-1) > | otherwise = map (c:) (rec (m-c,n-1,i)) ++ rec (m,n,i-1) > where c = coins!i In the f function, m is the amount of change to make, n is the number of coins that can be used, and i is the highest kind of coin that you are allowed to use. You can do most traditional dynamic programming problems this way. Enjoy, Chris

2 1

Re: Coin changing algorithm
by Yitzchak Gale 14 Jul '05

14 Jul '05

Actually, something along the lines of Dinh's attempted solution to the original partition problem is a very nice solution to the coin changing problem: Make change for the amount a, using at most k of the coins cs. > coins _ 0 _ = [[]] > coins _ _ 0 = [] > coins cs a k = [h:s | t <- init (tails cs), > let h = head t, > h <= a, > s <- coins t (a-h) (k-1)] (The functions "init" and "tails" are from the Data.List module.) Note that Dinh is already using a monad for his solution, via Haskell's special syntax for the List monad. Here it is translated into regular monad syntax: > coinsM _ 0 k = return [] > coinsM _ _ 0 = [] > coinsM cs a k = do > t <- init (tails cs) > let h = head t > unless (h <= a) [] > s <- coinsM t (a-h) (k-1) > return (h:s) (The function "unless" is from the Control.Monad module.) -Yitz

2 1

a simple function
by wenduan 14 Jul '05

14 Jul '05

Anyone please tell me what is wrong with the function: isEmpty ::[a]->Bool isEmpty xs | xs == [] = True |otherwise =False When I tried to load it into the interpreter,it says the following: Could not deduce (Eq a) from the context () arising from use of `==' at mylab2.hs:16 Probable fix: Add (Eq a) to the type signature(s) for `isEmpty' In a pattern guard for the definition of `isEmpty': xs == [] In the definition of `isEmpty': isEmpty xs | xs == [] = True -- X.W.D

9 15

RE: [Haskell] line-based interactive program
by Simon Marlow 13 Jul '05

13 Jul '05

On 08 July 2005 18:22, Olaf Chitil wrote: > In fact, unsafeInterleaveIO shows up limitations of the IO monad. > Without this strange primitive (what is actually unsafe about it?) Just picking up on this point: unsafeInterleaveIO is so named because it lets you write programs that don't obey the usual laws. For example: main = do r <- newIORef 0 a <- unsafeInterleaveIO $ readIORef r b <- unsafeInterleaveIO $ do writeIORef r 42; return 0 print (a + b) if you change (a + b) to (b + a), you get a different answer. Cheers, Simon

1 0

Confused about Cyclic struture
by Dinh Tien Tuan Anh 12 Jul '05

12 Jul '05

Hi, Im a newbie to Haskell and the concept of "cyclic strutures" has confused me a lot For example (taken from Richard Bird's book): ones = 1:ones Its clear that it involves a cyclic structure But: ones = repeat 1 repeat x = x:repeat x I dont really understand what the differences between these two and why the latter does not have a cyclic structure ? Why does changing : repeat x = xs where xs = x:xs create a cyclic stucture ? Thank you Anh _________________________________________________________________ Winks & nudges are here - download MSN Messenger 7.0 today! http://messenger.msn.co.uk

10 21

Overlapping Instances with Functional Dependencies
by Daniel Brown 11 Jul '05

11 Jul '05

I have the following three programs: class Foo a b instance Foo (a -> b) (a -> [b]) instance Foo a a class Bar a b | a -> b instance Bar (a -> b) (a -> b) instance Bar a a class Baz a b | a -> b instance Baz (a -> b) (a -> [b]) instance Baz a a When compiled in ghc 6.4 (with -fglasgow-exts -fallow-overlapping-instances -fallow-undecidable-instances) Foo and Bar compile fine, but Baz fails with this error: Baz.hs:2:0: Functional dependencies conflict between instance declarations: Baz.hs:2:0: instance Baz (a -> b) (a -> [b]) Baz.hs:3:0: instance Baz a a This is how I interpret the error: The fundep says "a uniquely determines b", but if you have `Baz (Int -> Int) b`, b is `Int -> [Int]` according to the first instance and `Int -> Int` according to the second instance. b isn't uniquely determined by a, so the functional dependency isn't functional -- thus the conflict. When confronted with overlapping instances, the compiler chooses the most specific one (if it is unique), e.g. `Baz (a -> b) (a -> [b])` is more specific than `Baz a a`. But it seems that the combination of the two features is broken: if the most specific instance is chosen before checking the functional dependency, then the fundep is satisfied; if the fundep is checked before choosing the most specific instance, then it isn't. Is this a bug, or am I confused? Dan

3 3

cabal --user question
by Frederik Eaton 11 Jul '05

11 Jul '05

Hi, How do I install a package in the user package.conf with cabal? It is not clear to me how to do this, looking at the output of 'configure --help'. There is an option "--user" to get dependencies from the user cabal file but this still, somewhat counterintuitively, tries to install the package in the global location (why would one want such behavior?). Specifying '--with-hc-pkg="ghc-pkg --user"' doesn't seem to work either, when I do this then 'install' and 'unregister' complete without error but apparently have no effect. Thanks in advance, Frederik

3 5

Re: matrix computations based on the GSL
by Keean Schupke 08 Jul '05

08 Jul '05

Is a matrix is a linear operation on a vector, does it not make sense to define matrix applicaion: mapply :: Matrix -> Vector -> Vector Then you can define say: rotate90 = mapply rotationMatrix90 v' = rotate90 v Keean.

2 3

RE: [Haskell-cafe] Overlapping Instances with Functional Dependencies
by Simon Peyton-Jones 08 Jul '05

08 Jul '05

Martin's dead right. GHC uses a less sophisticated mechanism to do matching when it's thinking about functional dependencies than when it's doing straight instance matching. Maybe something cleverer for fundeps would make sense, as you point out. I hadn't thought of that before; it's a good point. Nowadays, whenever a fundep question comes up I think "how would it show up if we had associated type synonyms instead of fundeps?" (see the paper on my home page). In this case I think the answer is "GHC's current instance-matching mechanism would work unchanged"; or to put it another way, what ever mechanism is used for instance matching, the same would be used for type dependencies. Simon | I wouldn't call this a bug, overlapping instances | and in particular the combination with functional dependencies | are something which is not well studied yet. | Hence, GHC is very conservative here. | | I feel like you, this program should work. | As you correctly point out, there's a conflict among the | two improvement rules (resulting from the instances and FD). | A sensible decision is to apply the same "ad-hoc" | mechanism to improvement rules that is currently | applied to overlapping instances. Of course, we need some | formal system to express such conditions precisely. | You find some hints how to achieve this in | | G. J. Duck, S. Peyton-Jones, P. J. Stuckey, and M. Sulzmann. | Sound and decidable type inference for functional dependencies. | In Proc. of ESOP'04 | | Martin | | | Daniel Brown writes: | > I have the following three programs: | > | > class Foo a b | > instance Foo (a -> b) (a -> [b]) | > instance Foo a a | > | > class Bar a b | a -> b | > instance Bar (a -> b) (a -> b) | > instance Bar a a | > | > class Baz a b | a -> b | > instance Baz (a -> b) (a -> [b]) | > instance Baz a a | > | > When compiled in ghc 6.4 (with -fglasgow-exts | > -fallow-overlapping-instances -fallow-undecidable-instances) Foo | > and Bar compile fine, but Baz fails with this error: | > | > Baz.hs:2:0: | > Functional dependencies conflict between instance declarations: | > Baz.hs:2:0: instance Baz (a -> b) (a -> [b]) | > Baz.hs:3:0: instance Baz a a | > | > This is how I interpret the error: The fundep says "a uniquely | > determines b", but if you have `Baz (Int -> Int) b`, b is `Int -> [Int]` | > according to the first instance and `Int -> Int` according to the second | > instance. b isn't uniquely determined by a, so the functional dependency | > isn't functional -- thus the conflict. | > | > When confronted with overlapping instances, the compiler chooses the | > most specific one (if it is unique), e.g. `Baz (a -> b) (a -> [b])` is | > more specific than `Baz a a`. | > | > But it seems that the combination of the two features is broken: if the | > most specific instance is chosen before checking the functional | > dependency, then the fundep is satisfied; if the fundep is checked | > before choosing the most specific instance, then it isn't. | > | > Is this a bug, or am I confused? | > | > Dan | > _______________________________________________ | > 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

2 1

RE: [Haskell-cafe] Re: [Haskell] ANNOUNCE: GHC survey results
by Simon Peyton-Jones 06 Jul '05

06 Jul '05

| If anything I would like to see the Haskell community produce a Haskell | front end which was compiler neutral. That would facilitate many | interesting projects, and that might even help with the need to support | new extensions as they come along. There are already some candidates | floating around, but it seems they are not widely adopted. Well, "ghc -c -fext-core Foo.hs" is a Haskell front end that produces System F code ("External Core"), in a file Foo.hcr. I'm not sure whether that was what you meant. However, External Core doesn't seem to have really caught on. Only 5% said it was essential, with another 16% saying "nice to have". I'm sure there's room to improve the ExtCore route. Simon

6 5