December 2003 - Haskell-Cafe

Re: To show or not to show french accents
by Jon Fairbairn 19 Dec '03

19 Dec '03

(note change of forum from glasgow-haskell-users) On 2003-12-19 at 12:28GMT MR K P SCHUPKE wrote: [ > I wrote: ] > >The problem is that if you are reading single bytes, 233 is > >not necessarily é. > > Erm, Internationalisation is not my thin as such... but I can't help > commenting that from a systems point of view this is an utterly bad > sitiation to be in... It certainly is. > I though Haskell used unicode? It's supposed to. Note that I said "/if/ you are reading a single byte", meaning that I was talking about the (not uncommon) curcumstance where the underlying operating system presents you with bytes each of which represents a single character (ie not something like utf-8). Haskell is supposed to deal with Unicode internally, but the I/O system's treatment of it is not currently in a happy state, at least partly because of what lies beneath. > I thought in unicode the id of a character was fixed > irrespective of language. It is. > Where is unicode support lacking? All over the place. There's this monstrous notion of "locale" that means that if you move your computer across the border from Germany into Poland and change the system settings appropriately, all character files change their meanings. It stems from files being untyped, and as all good Haskell programmers know, untyped is a Bad Thing. Jón -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk

1 0

Trace and loop examples?
by Vincenzo aka Nick Name 16 Dec '03

16 Dec '03

Hi all, I am trying to lear more about arrows in haskell, so I am reading the paper at: http://www.soi.city.ac.uk/~ross/papers/fop.html However, I can't understand how to produce a working and meaningful example of the trace function, or the loop arrow (I am using the "automata" example). The trace function is defined like: trace f b = let (c,d) = f (b,d) in c Can someone show an example function f to pass to trace and what the purpose is? Thanks Vincenzo

2 1

looking for data structure advice
by David Roundy 15 Dec '03

15 Dec '03

Hello everyone, I am trying to restructure some of my code to eliminate some O(n^2) operations, and have realized that this will require a change in how my data is represented, but I don't see any standard data types (in Data) that will really suit my needs. Currently I have a sequence of patches is just a list, so when two sequences or patches are reordered, I have an O(n^2) operation (where n is the length of each sequence). I would like to reduce this, since most patches are orthogonal, since they modify a single file, but this isn't possible as long as the data is represented in lists. What I'd like would be to have a data structure that holds an ordered list, but has a mapping from keys to its members, a sort of ordered FiniteMap. Each member would have to match several keys. I don't think this multiplicity of keys can be hidden in a single key, since I want to be able to search by any key in O(log n). Then I'd want to be able to extract its contents matching some keys, extractKeys :: [key] -> OrderedFiniteMap key elem -> [elem] with the above preserving the order of the elements. And to be able to modify only those patches matching a given key modifyOFM :: [key] -> a -> ((elem, a) -> ([key],elem,a)) -> OrderedFiniteMap key elem -> (OrderedFiniteMap key elem, a) where the second argument indicates how the first element to be modified changes, and possibly changes the keys when matching the second element... this is looking pretty complicated... maybe what I want is some sort of a monad. Of course I'd need "normal" access functions too, but those are more obvious. Is there an existing set of algorithms that might serve my needs (or some existing data structure, that would adequately suit my needs)? I really would rather not right my own data structure module for this purpose. Creating multiple references to a given data element to describe its list and all its keys is a bit intimidating... In case I haven't been clear enough, the algorithm I want to speed up looks like (when simplified a tad) commute :: ([Patch], [Patch]) -> Maybe ([Patch], [Patch]) commute (a:as, bs) = case commuteOneMany a bs of Nothing -> Nothing Just (bs', a') -> case commute (as, bs') of Nothing -> Nothing Just (bs'', as') -> Just (bs'', a':as') commuteOneMany a (b:bs) = case commuteOne a b of Nothing -> Nothing Just (b', a') -> case commuteOneMany a' bs of Nothing -> Nothing Just (bs', a'') -> Just (b':bs', a'') commuteOne :: Patch -> Patch -> (Patch, Patch) where there exists a function patchModifies :: Patch -> [Key] such that commuteOne a b | null (patchModifies a `intersect` patchModifies b) = (b, a) Any suggestions would be appreciated. At this point I've gotten myself pretty confused as to what exactly I want to do. :( -- David Roundy http://www.abridgegame.org

7 11

Importing strategies
by Henk-Jan van Tuyl 15 Dec '03

15 Dec '03

L.S., I am trying to compile the following program: > import Concurrent.Strategies > main = putStrLn "" Using the following command: ghc -v -package concurrent -package data -o "TryStrategies" "TryStrategies.lhs" -iC:/Programs/ghc-6.0.1/hslibs-imports > compile.log I receive the error message: TryStrategies.o(.text+0x22):fake: undefined reference to `__stginit_Concurrentzi Strategies_' What am I doing wrong here? -- Best regards, Henk-Jan van Tuyl

2 1

homework help: upn parser
by Max Hoffmann 15 Dec '03

15 Dec '03

Dear Haskell cafe members, I am somebody one could well call a bloody beginner but the elegance of functional programming and am therefore truly interested to learn more about Haskell. Now I have an assignment to write a parsing function to convert a string of a mathematical expression into a tree in UPN style to evaluate it afterwards. So my evaluating function looks like this: data Op = Plus|Minus|Times|Div|Fac deriving(Show,Eq) data OpTree = Term OpTree Op OpTree |Number Float |E deriving(Show,Eq) eval(Number z) = z eval(Term li op re) |op == Plus= (eval li) + (eval re) |op == Minus= (eval li) - (eval re) |op == Times= (eval li) * (eval re) |op == Div= (eval li) / (eval re) And I tried to write a parsing function but I got stuck in the very beginning. So far I wrote: --parsing parsing :: String->[OpTree] parsing (a:b:c:xs) t |isDigit b = ((parsing xs)) ((Term (read a) c (read b)):t) And the Hugs compiler gives me so many error messages, that I have no clue how to get rid of this mess. Could anybody give me a hint where my error is and whether I am right in the general direction. Thanks a lot for any kind of help, Max Hoffmann

2 1

Re: homework help: upn parser
by Leon Smith 15 Dec '03

15 Dec '03

Hi Max! This is a type definiton, which says that parsing takes one argument, a String, and gives you back a list of OpTree: > parsing :: String->[OpTree] > This is a function definition. The part before the = is called the left hand side, while the part after the = is called the right hand side. > parsing (a:b:c:xs) t > |isDigit b = ((parsing xs)) ((Term (read a) c (read b)):t) > > The (a:b:c:xs) is an example of a pattern. You are using the list constructor (:) to break down the list into individual items. According to your type definition, this argument is of type String, which is the same thing as [Char]. Thus, a, b, and c are bound to single characters, while xs is the bound to the rest of the string, assuming your string has at least three characters. If your string has less than three characters, then this pattern fails and the next clause in your function definiton will be tried. Then, according to your function definition, you then bind the second argument of the function to the variable "t". However, your type definition says you only have one argument. Since they disagree, this is an error. The right hand side of your function definition contains lots of errors, as you suggest. You probably want to rethink your type definition. I'd suggest the following: parsing :: String -> [OpTree] -> OpTree This says that parsing is a function that takes two arguments, a list of characters and a list of OpTrees, and returns a single OpTree. You are going to treat the second list argument like a stack. When you run across a number in your string, you are going to take the number off the string and push it onto the stack. When you run across an operation in your string, you are going to take two elements off the stack, combine the elements from the stack using the operation, and push the result back on the stack. Thus, your solution would contain this kind of structure: parsing ( string_with_number_in_front ) ( stack ) = parsing ( string_without_number ) ( Number (the_number) : stack ) parsing ( string_with_operation_in_front ) (last_element : next_element : rest_stack) = parsing ( string_without_operation ) ( Term last_element (the_operation) next_element : rest_stack ) Now, you must consider the boundary cases of the function "parsing". What I mean is, what kinds of clauses do you need for when you are done with recursion, and what should your first call to this function look like? Of course, you need to try out your code and carefully think about what it's doing. When asking for homework help on haskell-cafe, Haskellers have been known to introduce small intentional errors into their advice. Also, it's very impressive that Paul Natorp high school is using Haskell in it's coursework! In the United States, I've never heard of a high school that takes functional programming seriously. Sadly, many American universities don't take functional programming seriously either. Americans are really behind the game in this regard. Hope this helps. best, leon

1 0

Preventing/handling space leaks
by Henk-Jan.van.Tuyl 12 Dec '03

12 Dec '03

L.S., Does anyone know about documentation (preferably on the Web) on how to prevent/find/remove space leaks? Are there any differences between Hugs and GHC or any other Haskell platform, regarding space leaks? I read some discussions about why not everybody uses Haskell; it looks to me, that the problem of space leaks is a very good reason to not use Haskell for commercial applications. Java, for example, does not have this problem. -- Best regards, Henk-Jan van Tuyl

10 17

Re: import modules from a different directory
by Georg Martius 11 Dec '03

11 Dec '03

<moved to haskell-cafe> Hi, You can give GHC with -iPath a directory where to look for modules. With -v you see where GHC actually looks for libraries. Cheers, Georg On Thu, 11 Dec 2003 15:59:04 +0800 (GMT-8), Wang Meng <wangmeng(a)comp.nus.edu.sg> wrote: > Hi All, > > Anybody has the experience of importing a module from a different > directory?In my code, i need to import a module that is not in the > current > directory. How can I do that in GHC? > > > -W-M- > @ @ > | > \_/ > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0

type of (/) ?
by Yaroslav Korchevsky 10 Dec '03

10 Dec '03

I have been trying Hugs98 This is the average of floats list calculation program: ================================ accum :: [Float] -> Float accum list = foldr (+) 0 list my_avg list = (accum list) / (length list) ================================ While loading it I got the compiler message: ERROR "U:\slav\FP\Avg.hs":11 - Type error in application *** Expression : accum list / length list *** Term : accum list *** Type : Float *** Does not match : Int Why "accum list" should match to "Int"? When I try to replace (length list) with number - it works. ================================ my_avg list = (accum list) / 5 --works fine ================================ xx = 5 my_avg list = (accum list) / xx --doesn't work -- same message as above ================================ Possibly, I don't know something important, or Hugs is not quite mature? Thank you. Slav.

4 3

Re: Multiple functions applied to a single value
by Graham Klyne 09 Dec '03

09 Dec '03

A little while ago, I sent a long rambling message [1] containing a key question in response to an earlier helpful response. I guess my ramblings were quite reasonably passed over as too much waffle, and the question was lost. Here, I isolate the question. From the earlier response, I understand that: ((->) r) is an instance of Monad, but I haven't found a definition of the Monad instance functions. I think these do the job, and they satisfy the monad laws [2]: [[ instance Monad ((->) r) where return a = const a g1 >>= f = \e -> f (g1 e) e ]] Can anyone confirm, or point me at an actual definition? #g -- [1] http://haskell.org/pipermail/haskell-cafe/2003-November/005566.html [2] Checking the Monad laws for the above definitions (cf. Haskell report p90): (A) return a >>= k = [g1/const a][f/k] \e -> f (g1 e) e = \e -> k (const a e) e = \e -> k a e = k a -- as required. (B) m >>= return = [g1/m][f/const] \e -> f (g1 e) e = \e -> const (m e) e = \e -> (m e) = m -- as required. (C) m >>= (\x -> k x >>= h) = [g1/m][f/(\x -> k x >>= h)] \e -> f (g1 e) e = \e -> (\x -> k x >>= h) (m e) e = \e -> (k (m e) >>= h) e = \e -> ([g1/k (m e)][f/h] \e1 -> f (g1 e1) e1) e = \e -> (\e1 -> h (k (m e) e1) e1) e = \e -> h (k (m e) e) e (m >>= k) >>= h = ([g1/m][f/k] \e -> f (g1 e) e) >>= h = (\e -> k (m e) e) >>= h = [g1/(\e -> k (m e) e)][f/h] \e1 -> f (g1 e1) e1 = \e1 -> h ((\e -> k (m e) e) e1) e1 = \e1 -> h (k (m e1) e1) e1 = \e -> h (k (m e) e) e So both expressions are equivalent, as required. ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 2