August 2002 - Haskell-Cafe

Transformations of cyclic graphs [Was: Efficiency of list indices in definitions]
by oleg＠pobox.com 08 Aug '02

08 Aug '02

[Moved to Haskell-Cafe] Hello! Cycles sure make it difficult to transform graphs in a pure non-strict language. Cycles in a source graph require us to devise a way to mark traversed nodes -- however we cannot mutate nodes and cannot even compare nodes with a generic ('derived') equality operator. Cycles in a destination graph require us to keep track of the already built nodes so we can complete a cycle. An obvious solution is to use a state monad and IORefs. There is also a monad-less solution, which is less obvious: we can't add a node to the dictionary of constructed nodes until we have built the node, then means we can't use the updated dictionary when building descendants -- which need the dictionary when linking back. The problem can be overcome however with a credit card transform (a.k.a. "buy now, pay later" transform). To avoid hitting the bottom, we just have to "pay" by the "due date". The will use as an example the NFA->DFA transformation considered earlier. Perhaps we should first attempt a few obvious optimizations of a NFA/DFA recognizer. It seems that performance matters. finAuAcceptStringQ startStates string = or [faStateAcceptStringQ s string | s <- startStates] where faStateAcceptStringQ (FaState _ acceptQ _) [] = acceptQ faStateAcceptStringQ (FaState _ _ trans) (a:as) | null followerStates = False | otherwise = or [ faStateAcceptStringQ s as | s <- followerStates ] where followerStates = if a > (length trans) - 1 then [] else trans!!a Computing (length trans) when determining the followerStates is inefficient: even if 'a' is zero, we still have to traverse the whole list 'trans'. If our alphabet is binary, perhaps its better to specialize the FaState correspondingly and write: -- Automata over a binary alphabet data (Ord l,Show l) => FaState l = FaState {label :: l, acceptQ :: Bool, trans0:: [FaState l], trans1:: [FaState l]} -- Then a finite automaton is merely a list of starting FaStates: type FinAu l = [FaState l] --So, for example, an automaton equivalent to the regular expression --0*(0(0+1)*)* could be defined as: dom18 = [one] where one = FaState 1 True [one,two] [] two = FaState 2 True [two,one] [one,two] The acceptance function can be written as finAuAcceptStringQ start_states str = foldr (\l seed -> acceptP l str || seed) False start_states where acceptP (FaState _ acceptQ _ _) [] = acceptQ acceptP (FaState _ _ t0 t1) (s:rest) = finAuAcceptStringQ (if s then t1 else t0) rest We have simplified the original expression, and manually deforested it. test1= finAuAcceptStringQ dom18 $ map (>0) [0,1,0,1] test2= finAuAcceptStringQ dom18 $ map (>0) [1,1,0,1] test3= finAuAcceptStringQ dom18 [True] test4= finAuAcceptStringQ dom18 [False] It would be great to be able to compare and print the nodes: instance (Ord l,Show l) => Eq (FaState l) where (FaState l1 _ _ _) == (FaState l2 _ _ _) = l1 == l2 but printing a node is already a slight problem. We need to keep track of the already printed nodes to avoid looping. -- a data class for an occurrence check class OCC occ where empty:: occ a seenp:: (Eq a) => a -> occ a -> Bool put:: a -> occ a -> occ a -- Currently, it's just a list. -- In the future, we can pull in something fancier from the Edison instance OCC [] where empty = [] seenp = elem put = (:) -- Depth-first, pre-order traversal of the graph, keeping track of -- already printed nodes instance (Ord l,Show l) => Show (FaState l) where show state = "{@" ++ showstates [state] (empty::[FaState l]) "@}" where -- showstates worklist seen_states suffix showstates [] states_seen suffix = suffix showstates (st:rest) states_seen suffix | st `seenp` states_seen = showstates rest states_seen suffix showstates (st@(FaState l accept t0 t1):rest) states_seen suffix = showstate st $ showstates (t0++t1++rest) (st `put` states_seen) suffix showstate (FaState l accept t0 t1) suffix = "{State " ++ (show l) ++ " " ++ (show accept) ++ " " ++ (show $ map label t0) ++ " " ++ (show $ map label t1) ++ "}" ++ suffix Now, "print dom18" prints as [{@{State 1 True [1,2] []}{State 2 True [2,1] [1,2]}@}] For the NFA->DFA conversion, we need to keep track of already built states. -- A dictionary of states class StateDict sd where emptyd :: sd (l,FaState l) locate :: (Eq l) => l -> sd (l,FaState l) -> Maybe (FaState l) putd :: (l,FaState l) -> sd (l,FaState l) -> sd (l,FaState l) -- if performance matters, we can use a fancier dictionary from the Edison instance StateDict [] where emptyd = [] locate = lookup putd = (:) -- [nfa_state] -> dictionary_of_seen_states -> ([dfa_state],updated_dictionary) -- [dfa_state] is a singleton list determinize_cc states converted_states = -- first, check the cache case dfa_label `locate` converted_states of Nothing -> build_state Just dfa_state -> ([dfa_state],converted_states) where -- [NFA_labels] -> DFA_labels det_labels = sort . nub . (map label) dfa_label = det_labels states -- find out NFA-followers for [nfa_state] upon ingestion of 0 and 1 (t0_followers,t1_followers) = foldr (\st (f0,f1) -> (trans0 st ++ f0, trans1 st ++ f1)) ([],[]) states acceptQ' = or (map acceptQ states) -- really build the dfa state and return ([dfa_state],updated_cache) build_state = let -- node, dfa_state is computed _below_ converted_states1 = (dfa_label,dfa_state) `putd` converted_states (t0', converted_states2) = (determinize_cc t0_followers converted_states1) (t1', converted_states3) = (determinize_cc t1_followers converted_states2) dfa_state = (FaState dfa_label acceptQ' t0' t1') in ([dfa_state],converted_states3) finAuDeterminize states = fst $ determinize_cc states [] At the heart of the credit card transform is the phrase converted_states1 = (dfa_label,dfa_state) `putd` converted_states we added to the dictionary of the computed states the state that we haven't built yet. Because (,) is non-strict in its arguments and `locate` is non-strict in its result, we can get away with a mere promise to "pay". We can print the DFA for dom18 to see what we've got: finAuDeterminize dom18 -- shows [{@{State [1] True [[1,2]] [[]] } {State [1,2] True [[1,2]] [[1,2]]} {State [] False [[]] [[]] }@}] which is a DFA (which happens to be minimal) recognizing (0+1)* - 1(0+1)* An example from the original message: dom19 = [one,two] where one = FaState 1 True [two] [] two = FaState 2 True [one] [one] finAuDeterminize dom19 -- shows [{@{State [1,2] True [[1,2]] [[1]] } {State [1] True [[2]] [[]] } {State [2] True [[1]] [[1]] } {State [] False [[]] [[]] }@}] which recognizes (0+1)* - (0+1)*11(0+1)*

1 0

Modification of State Transformer
by Shawn P. Garbett 08 Aug '02

08 Aug '02

I'm trying to modify Richard Bird's state transformer. The example in his book (_Introduction_to_Functional_Programming_using_Haskell_) has State defined as a explicit type. I.e. Here's the relevant snippet: -- State transformer definition newtype St a = MkSt (State -> (a, State)) type State = Int -- State transformer applied to state apply :: St a -> State -> (a, State) apply (MkSt f) s = f s -- State monad instance Monad St where return x = MkSt f where f s = (x,s) p >>= q = MkSt f where f s = apply (q x) s' where (x, s') = apply p s ----------------------------------------- What I want is something like this, so that the state transformer has a generic state type: newtype St a s = MkSt (s -> (a, s)) apply :: St a s -> s -> (a, s) apply (MkSt f) s = f s instance Monad St where return x = MkSt f where f s = (x,s) p >>= q = MkSt f where f s = apply (q x) s' where (x, s') = apply p s ----------------------------------------------------------- The trouble occurs on the instance line Couldn't match `*' against `* -> *' Expected kind: (* -> *) -> * Inferred kind: (* -> * -> *) -> * When checking kinds in `Monad St' In the instance declaration for `Monad St' Failed, modules loaded: none.

3 3

Unicode
by ck15 08 Aug '02

08 Aug '02

Hi, Is there a way to include symbols like set union , set intersection etc in Haskell code ? Chitra

3 2

Jcreator
by Scott J. 05 Aug '02

05 Aug '02

Hi, can Jcreator be used also with GHC or only with Hugs as an IDE for Haskell? Thx Scott

1 0

multiple C compilers
by Scott J. 05 Aug '02

05 Aug '02

Hi, This is perhaps an idiot question , but I would like to know if one has to stick with one c compiler or if one can use different c compilers for Haskell2C ? Thx Scott

1 0

freeTR.com Artist olmak icin evden kacan Turk kizlarinin Beyoglunda cekilmis Acik sacik Cinsel birlesme iceren Videolari Date: Sun, 04 Aug 2002 19:57:21 +0300
by mimi 04 Aug '02

04 Aug '02

http://www.freeTR.com Artist olmak icin evden kacan Turk kizlarinin Beyoglunda cekilmis Acik sacik Cinsel birlesme iceren Videolari icin: http://www.freeTR.com

1 0

Fw: extenssions of Haskell
by Scott J. 03 Aug '02

03 Aug '02

Hi, I have allready read a lot of Haskell 98. What I cannot find are papers about the State transformer monad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GTK2? bindins. Are rpms for redhat also installable for MandrakeLinux .? Are there Haskell IDE's ? Sorry for thr typo's ----- Original Message ----- From: Scott J. To: haskell-cafe(a)haskell.org Sent: Sunday, August 04, 2002 1:41 AM Subject: extenssions of Haskell Hi, I have allrewdy read a lot of Haskell 98. What I cannot find are papers about the State transformermonad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GYK2? bindins. Are rpms for redhat also installable for MandrakeLinux .?

1 0

extenssions of Haskell
by Scott J. 03 Aug '02

03 Aug '02

Hi, I have allrewdy read a lot of Haskell 98. What I cannot find are papers about the State transformermonad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GYK2? bindins. Are rpms for redhat also installable for MandrakeLinux .?

1 0

[Xemacs] x-symbol mode for Haskell
by Jorge Adriano 03 Aug '02

03 Aug '02

Hi, I've always liked the X-Symbol package for Xemacs http://x-symbol.sourceforge.net/ I've searched for Haskell X-Symbol modes, but there doesn't seem to be one. It's kind of strange because it seems to me like most people who are into haskell would like to use non-ascii symbols like greek letters and some nice looking operators - just take a look at some haskell books, LaTeX modes for haskell etc. I tried to hack an x-symbol haskell mode. *I know nothing about elisp* or x-symbol internals so the mode is bloated with useless stuff and *does not works* properly (yet?). It is in fact just a very dirty non working hack... right now I just can't spend much time with it. I thought I'd ask if anyone (preferably with more experience :) is doing, or thinking about doing some good haskell x-symbol mode. J.A. P.S.: Just in case you want to take a look at it here to understand what it is supposedd to do, it goes in attchment. After installing it try typing something like f :: Num _alpha => [_alpha] -> [_alpha] f x = x+x The _alphas will turn into real alphas as you type them, the => and -> will also turn into good looking non-ascii arrows. :) The main problem is that the source file is not beeing saved correctly (decode token works, but not encode token), so you're not going to be able to compile it. Of course there are many other problems like <= turning into an arrow instead of a "less than equal", etc etc etc :) How to install it: X-Symbol: - download the latest x-symbol version. - run xemacs as root - M-x package-admin-add-binary-package (it will tell you the directory where it is installed) The quick-dirty-non-usable-x-symbol-haskell-mode :) - save the "x-symbol-haskell.el" and "x-symbol-hooks.el" files - compile them (open in xemacs, right click buffer, byte-compile this file) - copy (as root) the .el and .elc files to the directory where your other x-symbol .el and .elc files are. You may want to back up your old "x-symbol-hooks.el" file. To "use" it just "M-x x-symbol-mode" in an haskell buffer and type away.

1 0

RE: can a lazy language give fast code?
by Simon Marlow 31 Jul '02

31 Jul '02

> Can one write withthe Haskell compliler faster code than in > the examples of http://www.bagley.org/~doug/shootout/ where > GHC (old Haskell 98?) seems to be much slower than Ocaml or > Mlton both strict functional languages. > Can one expect any improvements in speed in the future? Many of those programs can be written differently to improve performance. One issue that is affecting performance in several cases is the speed of character I/O, and the representation of Strings as lists of characters. Dramatic improvements can be had by using unboxed arrays of Char (Data.Array.Unboxed), or PackedString (which these days is implemented using unboxed arrays in GHC). Cheers, Simon

6 10