- Haskell-Cafe - Haskell.org

Haskell-Cafe -- confirmation of subscription -- request 321501
by Cyril Baratoff 09 Aug '02

09 Aug '02

1 0

Combining type constraints
by Andrew J Bromage 09 Aug '02

09 Aug '02

G'day all. I have a large number of functions all of which use the same set of type constraints, such as: > foo :: (Monad m, Ord t, Show t) => ... Ideally, I'd like to combine them into one typeclass. At the moment, I'm using the equivalent of: > class (Monad m, Ord t, Show t) => Constraints m t where { } > instance (Monad m, Ord t, Show t) => Constraints m t where { } > foo :: (Constraints m t) => ... This requires undecidable instances. Is there a way to do this that doesn't require non-98 features apart from multi-parameter type classes? If not, is there an argument for a language construction which supports this idiom, analogous to type synonyms, except for type classes? Cheers, Andrew Bromage

1 0

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. 06 Aug '02

06 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