- Haskell-Cafe - Haskell.org

RE: [Haskell-cafe] Re: Module.T naming style
by Simon Marlow 15 Jul '05

15 Jul '05

On 15 July 2005 09:48, Henning Thielemann wrote: > On Thu, 14 Jul 2005, Andrew Pimlott wrote: >> 2) enshrining one-type-per-module in the naming convention is not IMO >> justified, and may prove limiting; > > Other languages like Modula-3 and Oberon do it with great success. The > limit in Haskell is that most compilers don't conform to the Haskell > 98 report which allows mutually recursive modules. But I think the > compilers should allow them instead of forcing users to put many type > and class definitions into one module. I hope you weren't including GHC in "most compilers" :-) GHC's implementation of mutually recursive modules is conformant with Haskell 98 (see Section 5.7). Cheers, Simon

3 2

RE: [Haskell-cafe] Module.T naming style
by Simon Marlow 15 Jul '05

15 Jul '05

On 15 July 2005 11:24, Henning Thielemann wrote: > On Fri, 15 Jul 2005, Simon Marlow wrote: > >> On 15 July 2005 09:48, Henning Thielemann wrote: >> >>> The limit in Haskell is that most compilers don't conform to the >>> Haskell 98 report which allows mutually recursive modules. But I >>> think the compilers should allow them instead of forcing users to >>> put many type and class definitions into one module. >> >> I hope you weren't including GHC in "most compilers" :-) GHC's >> implementation of mutually recursive modules is conformant with >> Haskell 98 (see Section 5.7). > > But there are unresolved problems with class definitions. > http://www.haskell.org/pipermail/haskell-cafe/2005-May/009873.html > > Is this covered by the statement "Modules may be mutually recursive."? > http://www.haskell.org/onlinereport/modules.html Ok, mututal recursion between classes in separate modules isn't currently supported (I'd forgotten about that). But it's a bit harsh to say that because of this missing feature GHC doesn't support mutually recursive modules - we've been using mutually recursive modules in GHC itself for nearly a decade! Cheers, Simon

1 0

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

15 Jul '05

ChrisK wrote: > During a single evaluation the recursive calls never "collide", so > unless this overlap is optimized, then the subproblem memoizing won't do > anything... Actually, the recursive calls can collide. For example, if you are trying to make 87 cents with 7 coins, you can make the first 80 cents with four coins using either 50-10-10-10 or 20-20-20-20. Either way, you'll end up making a recursive call on 7 cents and 3 coins. Admittedly, however, with this choice of coin denominations, you don't get very many such collisions... -- Chris

1 0

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

15 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 12 Jul '05

12 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