August 2002 - Haskell

Re: UTF-8 library
by Ashley Yakeley 07 Aug '02

07 Aug '02

At 2002-08-07 02:28, Axel Simon wrote: >encodeISO-8859-1 :: String -> [CChar] Word8, not CChar. -- Ashley Yakeley, Seattle WA

3 2

Re: one C compiler
by Scott J. 07 Aug '02

07 Aug '02

Yes I want to make Code written in C available to Haskell. But I worry bow about mixing different C compilers. E.g. for Windows there is a retargettable C compiler made by Jacob Navia available for a low price (it is even free). See http://www.q-software-solutions.com/ .And on the other hand Microsoft bundles all his compilers in Visual Studio. net . I don't know if I can use code from C# available to Haskell. Regards Scott ----- Original Message ----- From: "Lars Lundgren" <d95lars(a)dtek.chalmers.se> To: "Scott J." <jscott(a)planetinternet.be> Sent: Wednesday, August 07, 2002 10:14 AM Subject: Re: one C compiler > On Tue, 6 Aug 2002, Scott J. wrote: > > > Hi, > > > > I want to know if I have to use the same c compiler with which GHC was > > ported to windows or may I use other C compilers for poting C to GHC? > > > > It is very hard to understand what it is you are asking. GHC is a compiler > written in Haskell (Not C). What is it you are trying to do? Make some > code written in C available to some code written in Haskell, or what? > > > /Lars L > > >

1 0

Re: Efficiency of list indices in definitions
by Carl McTague 07 Aug '02

07 Aug '02

> Date: Wed, 7 Aug 2002 10:24:45 +1000 > From: Andrew J Bromage <ajb(a)spamcop.net> > > > A large part of what I'm looking for at the moment is simply to find a > > fast and efficient way to express cyclic graphs in Haskell because in > > a present research project I need to manipulate machines with hundreds > > and thousands of states and my current, simple implementation simply > > won't do: my jobs balloon in size and die. > > Using linear search to look up states is going to cause you > prohibitively bad behaviour beyond 30 or so states no matter what you > do. Some possibilities are: FGL (as previously mentioned), a > dictionary structure like FiniteMap or clever use of IORefs. OK, I guess I'll look into the FGL, FiniteMap and perhaps even (gasp) IORefs... > As a matter of interest, is all you are doing here converting regular > expressions into DFAs? If so, a modern algorithm which doesn't go > via NFAs might help a bit. I have some code if you would like it. Thanks for offering. I'm actually not doing regexp -> nfa (although I do dfa -> regexp followed by rewrite simplification to get nice, textual representations of machines). I'm actually studying periodic orbits of a special class of operators on regular language space. Carl

1 0

Re: UTF-8 library
by George Russell 07 Aug '02

07 Aug '02

Ashley Yakeley wrote [snip] > Text encoded with ISO 8859-1 or UTF-8 is octets. If you want to use > CChars, you should then subsequently convert the Word8s into CChars. We were talking about converting CStrings, which are necessarily sequences of CChars. I have to say I do not relish the prospect of replacing the current peekCString interface by three functions which (1) translate a CString/CStringLen into [CChar] (2) translate a [CChar] into a [Word8] (3) translate a [Word8] into a String (and of course the inverse functions to go in the other direction.) If we want to do this, we certainly need to keep the existing functions since I certainly don't want to have to pass a String through three separate transformations just to make it suitable for C.

2 1

SURVEY - Haskell editing (summary)
by Claus Reinke 07 Aug '02

07 Aug '02

I sent out the summary of results of our little Haskell editing survey yesterday, but they are still being held for moderator approval because of slight oversize.. While our moderator seems to be unavailable (hi, there!-), you can also find the summary from our project web page. Cheers, Claus "Refactoring Functional Programs" http://www.cs.ukc.ac.uk/research/groups/tcs/fp/Refactor/ ----- Original Message ----- From: <haskell-admin(a)haskell.org> To: <claus.reinke(a)talk21.com> Sent: Tuesday, August 06, 2002 11:01 PM Subject: Your message to Haskell awaits moderator approval > Your mail to 'Haskell' with the subject > > SURVEY - Haskell editing (summary) > > Is being held until the list moderator can review it for approval. > > The reason it is being held: > > Message body is too big: 22995 bytes but there's a limit of 20 KB > > Either the message will get posted to the list, or you will receive > notification of the moderator's decision. >

1 0

Concurrency and Haskell
by mgross＠dorsai.org 07 Aug '02

07 Aug '02

A group of us at Brooklyn College (City University of New York) are in the latter stages of setting up a Mosix cluster that we would like to use for research on, among other things, parallel execution of Haskell code and run-time optimization of both automatic and programmed parallelization. I would greatly appreciate hearing from anyone who can provide advice on an appropriate bibliography on the language implementation and past work in this area (other than the code in the Haskell compilers and libraries, of course), approaches, ongoing work, etc. Also, I would be most interested in hearing from anyone interested in joining our effort (no problems with remote access to the cluster by way of SSH), or making arrangements for cooperation in research in this area, although, of course, access to our equipment will be subject to approval from "higher authorities" (however, note that I really don't expect difficulty here, since our administration has already shown considerable interest in supporting the project). Replies to the list will be read, but those who wish may mail me directly at mgross(a)dorsai.org. Thanks in advance for any replies. Murray Gross Adj. Lecturer, Brooklyn College, City University of New York

2 1

Mailing List
by Adriano Ricardo Duma 07 Aug '02

07 Aug '02

Hi, my name is Adriano and i am a student of science computer. I liked to your accept to mailing list for teaching futures. Thanks. PS: my english is not very good, sorry. ------------------------------------------------------ ADRIANO RICARDO DUMA PUCPR - Pontifícia Universidade Católica do Paraná www.pucpr.br LAMI - Laboratório de Mídias Interativas http://www.lami.pucpr.br/users/adriano ------------------------------------------------------ ------------------------------------------------- This mail sent through IMP: http://horde.org/imp/

1 0

Re: OT: haskell, .net, microsoft and vs
by Rijk J. C. van Haaften 07 Aug '02

07 Aug '02

>> What I'm more intersted in right now is this: they have an *excellent* >> development environment (Visual Studio) and have had it for years. But, >> as far as I know, ... I really >> couldn't use it to develop applications in any of the languages listed >A couple of years ago, I saw a demo of Visual Studio for Haskell, >based on links to a running Hugs interpreter. Daan Leijen was the >author, and I believe he later spent some time at Microsoft in Redmond, >specifically working with the Visual Studio programming team. However, >I suspect that VS for Haskell was more of a side interest and not a >real product for release. Daan, would you like to comment further? Well Daan is very, very, very busy, so I'll anser in his place. Visual Haskell, as Daan calls it, was (is) rather well suited as a real product for release, but licensing problems keep him from distributing it. Rijk-Jan van Haaften Utrecht University

1 0

Re: UTF-8 library
by Ashley Yakeley 07 Aug '02

07 Aug '02

At 2002-08-07 03:03, Axel Simon wrote: >> Text encoded with ISO 8859-1 or UTF-8 is octets. If you want to use >> CChars, you should then subsequently convert the Word8s into CChars. >Then I hope there is no C implementation where char is less than 8 bits >long. There may or may not be. Squeezing in octets from ISO 8859-1 encoding is a problem you'll have to deal with either way, and is entirely separate from the text encoding process. -- Ashley Yakeley, Seattle WA

1 0

Re: Efficiency of list indices in definitions
by oleg＠pobox.com 07 Aug '02

07 Aug '02

Carl McTague wrote: > finAuDeterminize :: (Ord l) => FinAu l -> FinAu [l] > finAuDeterminize startStates = [f startStates] > where f :: (Ord l) => [FaState l] -> FaState [l] > f states = FaState label' acceptQ' trans' > where label' = sort (map label states) > acceptQ' = or (map acceptQ states) > trans' = map (singleton.f.concat) (transpose (map trans states)) > singleton a = [a] > Now, we get to the heart of my question. This definition is quite > lovely, recursive and lazy, but it doesn't actually capture the > recurrent structure of the resulting automata. That is, if we were to > compute: > finAuAcceptStringQ (finAuDeterminize dom18) somestring > then finAuDeterminize would keep spinning out, generating more and > more states, which would actually be equivalent (and, have identical > state labels). To prevent such a behavior we ought to keep track of the states that we have already computed. Before getting to the solution, I'd like to take the liberty to modify your definition for the FSM to improve readability (at the expense of efficiency). I'd like to be able to print automata, to see what exactly I have determinized. data FaState l = FaState {label :: l, acceptQ :: Bool, trans :: [[l]]} deriving(Eq,Show) -- states start states data FA l = FA [(l,FaState l)] [l] deriving Show The transition function is now the list of labels rather than the list of states. A naive NFA recognizing a sample 0*(0(0+1)*)* can be written as dom18 = FA [(1,one), (2,two)] [1] where one = FaState 1 True [[1,2],[]] two = FaState 2 True [[2,1],[2,1]] (BTW, I had trouble with the automaton in the original article. That NFA recognized [1], which it should not). The acceptance function can be written as finAuAcceptStringQ :: (Eq l) => FA l -> [Int] -> Bool finAuAcceptStringQ (FA all_states start_labels) str = or [acceptP (locate_state l) str | l <- start_labels] where locate_state l = let (Just state) = lookup l all_states in state acceptP (FaState _ acceptQ _) [] = acceptQ acceptP (FaState _ _ trans) (a:as) = or [ acceptP (locate_state l) as | l <- followerStates ] where followerStates = if a > (length trans) - 1 then [] else trans!!a The determinizer can then be written as follows: finAuDeterminize (FA all_states start_labels) = FA all_states' [start_label'] where -- [NFA_labels] -> DFA_labels det_labels = sort . nub start_label' = det_labels start_labels -- DFA states all_states' = build_states [start_label'] [] -- build_states labels seen_labels -- lazily builds the list of DFA states. 'labels' is the list -- of labels for the states to build. seen_labels are the labels -- of the states we have built already build_states [] seen_labels = [] build_states (l:labels) seen_labels = if l `elem` seen_labels then -- already built DFA state l build_states labels seen_labels else really_build l labels seen_labels -- Build a DFA state with a label 'dfa_label' and return a list -- of the constructed state and a promise to build the follower states really_build dfa_label labels seen_labels = (dfa_label,dfa_state): build_states new_labels (dfa_label:seen_labels) where dfa_state = FaState dfa_label acceptQ' trans' locate_state l = let (Just state) = lookup l all_states in state nfa_states = map locate_state dfa_label acceptQ' = or (map acceptQ nfa_states) trans' = map ((:[]).det_labels.concat) $ transpose $ map trans nfa_states new_labels = (concat trans') ++ labels test1' = finAuAcceptStringQ (finAuDeterminize dom18) [0,1,0,1] test2' = finAuAcceptStringQ (finAuDeterminize dom18) [1,0] The states of the output DFA are built lazily. Each state is constructed only once. To see that equivalent states are not duplicated, we can check the result of determinizing the dom18: finAuDeterminize dom18 prints FA [([1], FaState{label=[1], acceptQ=True, trans=[[[1,2]],[[]]]}), ([1,2], FaState{label=[1,2],acceptQ=True, trans=[[[1,2]],[[1,2]]]}), ([], FaState{label=[], acceptQ=False,trans=[]})] [[1]] -- the starting state which is indeed a DFA (and so happens, the minimal one).

4 4