- Haskell-Cafe - Haskell.org

Permutation with k levels
by Nuno Pinto 07 Nov '06

07 Nov '06

Hi all, I am coding a zip application (using huffman algorithm) for academic reasons. In the process i needed a permute function that i coded but disliked a lot.. I went to the internet looking for a good generic permute algorithm in haskell the best one i found was not generic at all: import List perms [] = [[]] perms (x:xs) = [ p ++ [x] ++ s | xs' <- perms xs , (p, s) <- zip (inits xs') (tails xs') ] I also found information regarding this subject in: http://www.haskell.org/hawiki/PermutationExample What am i coding in specific? I receive a list in the form: -- l1 is a pair of the identifier and the associated probability l1 = [("A",0.6),("B",0.2)] I must return the permutation with k levels; for example: -- permute l k = ... -- should return permute l1 0 = [] permute l1 1 = l1 permute l2 2 = [("AA",0.64),("AB",0.16),("BA",0.16),("BB",0.04)] permute l3 3 = [("AAA", Pa*Pa*Pa), ("AAB",Pa*Pa*Pb),("ABA",...),("ABB",...),("BAA",...),("BAB",...),("BBA",...),("BBB",...)] --where: -- 0.64 = Pa*Pa -- 0.16 = Pa*Pb -- 0.04 = Pb*Pb All of my friend are developing this in c... Of course its easier but i have enough of c and c# at work, so I'm doing this in haskell, the way i like it :) For all interested in huffman coding: http://en.wikipedia.org/wiki/Huffman_coding Thanks in advance for the help, and greetings to all! Nuno P.s. Follows the code i developed until now.. Its open source :P Just hope no-one submit the same work as i did :P -- <resumo>-- Este modulo define uma ferramenta de compressão usando para o -- efeito o algoritmo de Huffman.---- HZip quer dizer isso mesmo: HuffmanZip.-- </resumo>module HZip where import List -- #region Notas-- . Ver parte de compressão/rendimento pois pode ter boas dicas para eficiência.-- #endregion -- #region Constantes para efeitos de teste.-- <resumo>-- Listas usadas para efeito de teste.-- </resumo> l1 = [("b",0.15),("d",0.08),("f",0.02),("g",0.01),("e",0.08),("c",0.15),("a",0.5),("h",0.01)] l2 = [("a",0.8),("b",0.2)]-- #endregion -- #region Funções Auxiliares-- <resumo>-- Função que testa a convergência de funções.-- Quando o valor da próxima iteração é igual ao da anterior-- devolve o resultado respectivo.---- Da autoria de jas<at>di<dot>uminho<dot>pt-- </resumo>-- <variavel termo='f'>-- A função a aplicar recursivamente.-- </variavel>-- <variavel termo='s'>-- A solução actual do problema.-- </variavel>-- <devolve>-- O resultado final da operação.-- </devolve>-- limit :: (a -> a) -> a -> a limit f s | s == next = s | otherwise = limit f next where next = f s -- <resumo>-- Calcula a metade das probabilidades.-- </resumo>-- <variavel termo='l'>-- A lista de probabilidades.-- </variavel>-- <devolve>-- O total das probabilidades a dividir por 2.-- </devolve> metade l = (sum l) / 2 -- <resumo>-- Devolve o primeiro elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O primeiro elemento.-- </devolve> fst3 (a,_,_) = a -- <resumo>-- Devolve o segundo elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O segundo elemento.-- </devolve> snd3 (_,b,_) = b -- <resumo>-- Devolve o terceiro elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O terceiro elemento.-- </devolve> trd3 (_,_,c) = c-- #endregion -- #region Funções: Teoria da informação-- <resumo>-- Calcula a quantidade de informação de uma determinada mensagem.-- </resumo>-- <variavel termo='p'>-- A probabilidade da mensagem.-- </variavel>-- <devolve>-- A quantidade de informação da mensagem.-- </devolve>-- i :: Float -> Float i p = logBase 2 (1/p) -- <resumo>-- Entropia, função que calcula a informação média por mensagem.-- </resumo>-- <variavel termo='l'>-- A lista de probabilidades.-- </variavel>-- <devolve>-- A informação média por mensagem.-- </devolve>-- h :: [Float] -> Float h l = sum $ map (\p -> if p == 0 then 0 else p * i p) l -- <resumo>-- Calcula o comprimento médio do código (N).-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- p -> Probabilidade do acontecimento.-- c -> Comprimento da palavra código.-- </variavel>-- <devolve>-- O comprimento médio do código.-- </devolve>-- n :: [(Float,Int)] -> Float n l = sum $ map (\(c,p) -> p * c) l -- <resumo>-- Desigualdade de Kraft.-- </resumo>-- <variavel termo='l'>-- A lista de comprimento das palavras código.-- </variavel>-- <devolve>-- True, se o código binário for univocamente decifravel-- False caso contrário.-- </devolve>-- kr :: [Int] -> Bool kr l = 1 >= sum ( map (\n -> 2^^(-n)) l ) -- <resumo>-- Algoritmo dos códigos de Huffman.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <devolve>-- Tuplo do tipo (t,n,b) em que:-- t -> Tabela de Huffman resultante.-- n -> Comprimento médio do código.-- b -> Se o código resultante é unívocamente decifravel.-- </devolve>-- huffman :: [(String,Float)] -> ([(String,Float,[Int])], Float, Float, Bool) huffman l = (tabHuffman,n lProbTam,kr lTamanhos) where lProbTam = map (\(c,p,b) -> (p,fromIntegral(length b))) tabHuffman lTamanhos = map (\(c,p,b) -> (length b)) tabHuffman tabHuffman = concat $ limit passo5 [map (\(c,p) -> (c,p,[])) (passo1 l)] -- <resumo>-- Ordena as mensagens por ordem decrescente de probabilidade.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <devolve>-- A lista ordenada por ordem decrescente de probabilidade.-- </devolve>-- passo1 :: [(String,Float)] -> [(String,Float)] passo1 l = sortBy (\(_,p1) (_,p2) -> compare p2 p1) l -- <resumo>-- Repete o calculo para cada um dos subconjuntos.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p,b) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- b -> Lista de inteiros com o binário correspondente.-- </variavel>-- <devolve>-- A lista ordenada por ordem decrescente de probabilidade.-- </devolve>-- passo5 :: [(String,Float,[Int])] -> [(String,Float,[Int])] passo5 l@(h:[]) = (passo234 0 (metade (map (\(_,p,_) -> p) h)) h (length h) [] []) passo5 l@(h:t) = (passo234 0 (metade (map (\(_,p,_) -> p) h)) h (length h) [] []) `union` (passo5 t) -- <resumo>-- Divide os subconjuntos cada um com apróximadamente métade da probabilidade-- mantendo a ordenação. Em seguida atribui o código binário e termina a codificação-- para o subconjunto se este tiver apenas um elemento.-- </resumo>-- <variavel termo='ac'>-- O acumulador de probabilidade.-- </variavel>-- <variavel termo='e'>-- Sublista a esquerda.-- </variavel>-- <variavel termo='d'>-- Sublista a direita.-- </variavel>-- <variavel termo='n'>-- Define o comportamento de paragem caso sublista tenha comprimento 1.-- </variavel>-- <variavel termo='l'>-- O calculo actual da tabela de huffman.-- </variavel>-- <devolve>-- Um passo da tabela de huffman.-- </devolve>-- passo234 :: Float -> Float -> [(String,Float,[Int])] -> Int -> [(String,Float,[Int])]-- -> [(String,Float,[Int])] -> [[(String,Float,[Int])]] passo234 _ _ [] _ e [] = [e] passo234 _ _ [] _ e d = [e]++[d] passo234 _ _ (h:t) 1 e d = passo234 0 0 [] 1 [h] d passo234 ac met l@((c,p,b):t) n [] d = passo234 (ac+p) met t n [(c,p,b++[0])] d passo234 ac met l@((c,p,b):t) _ e d | ac < met = passo234 (ac+p) met t 2 (e++[(c,p,b++[0])]) d |otherwise = passo234 (ac+p) met t 2 e (d++[(c,p,b++[1])]) -- <resumo>-- Codifica por blocos conforme um factor.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- k = 1, codificação = 8 bits.-- k = 2, codificaçao = 16 bits.-- k = 3, codificação = 32 bits.-- k = n, cofificação = 2^(n+2) bits.-- </variavel>-- <devolve>-- A tabela de huffman associada,-- H (fonte),-- N,-- Se o codigo gerado é unívocamente decifravel.-- </devolve>-- permute deve ser subsituido por (permute l k) blocos l k = (fst3 tabHuffman, h (map snd l), (snd3 tabHuffman)/k, trd3 tabHuffman) where tabHuffman = huffman permute -- <resumo>-- Cria as permutações da de simbolos e calcula a probabilidade associada.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- Número de niveis.-- </variavel>-- <devolve>-- Uma lista com os novos simbolos (codificação por blocos) e a respectiva-- probabilidade.-- </devolve> permute = [("aa",0.64),("ab",0.16),("ba",0.16),("bb",0.04)] -- <resumo>-- Calcula a compressão num determinado passo.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- Número do passo.-- </variavel>-- <devolve>-- Percentagem de compressão.-- </devolve> compressao l k = (nf - n_)/nf where nf = snd3 (huffman l) n_ = trd4 (blocos l k) trd4 (_,_,c,_) = c-- #endregion _________________________________________________________________ Windows Live Spaces is here! It’s easy to create your own personal Web site. http://spaces.live.com/signup.aspx

5 5

Efficiency of bang patterns
by Chad Scherrer 07 Nov '06

07 Nov '06

I'm curious about the implementation of bang patterns, and the implications for performance. Previously on this list, Lemmih has pointed out that throwing in an extra `seq` here and there to force strictness is a bad idea, unless you do it very carefully. He points out that the strictness analyzer will catch a lot of cases without a need for seq. But the approach of compiling without any `seq`s, looking for leaks, and then adding them in one at a time seems tedious. There should be a more predictable, more uniform way of achieving strictness. Is it reasonable to promote a programming style where strictness is achieved using strictness annotations and bang patterns? I find it very appealing that the "!" syntax translates so nicely from type declarations to patterns. I had originally thought that every bang pattern was translated into a seq call, as a sort of preprocessing step, but from this page... http://hackage.haskell.org/trac/haskell-prime/wiki/BangPatterns ... is is clear that in many cases a bang pattern can be rewritten as a case statement, which seems to me an opportunity to avoid some code ugliness. In cases semantically distinct from a case statement, maybe something like the following could be done, or maybe is already... 1. Pass the expression to the strictness analyzer, without the bang pattern. 2. If it's already strict, great! We're done. 3. If not, add an extra seq call. Now, I'm no compiler expert (obviously, I suspect), and maybe I've misunderstood the role of the strictness analysis step. But being able to easily make things really strict seems pretty important, and there seem to be a lot of subtleties to using seq that make it difficult to tune for performance. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Announcements list
by Diego Navarro 07 Nov '06

07 Nov '06

There should be a separate, moderated Haskell-announcements list. I filter out haskell-cafe into a folder and read it separately from my main inbox, but I'd like to have important announcements directly into my inbox, and haskell(a)haskell.org still has some chatty questions-and-answers sessions. -- Diego Navarro/syntaxfree

3 2

[ghc 6.6] Where is FGL now?
by Stephane Bortzmeyer 06 Nov '06

06 Nov '06

In ghc 6.4, I used Data.Graph.Inductive (aka FGL): % ghc-pkg list /usr/lib/ghc-6.4/package.conf: ... fgl-5.2, ... In ghc 6.6, it seems it disappeared. ghc-pkg list does not show it, the compiler says "Could not find module `Data.Graph.Inductive'" but it is still documented in http://www.haskell.org/ghc/docs/latest/html/libraries/index.html and the ghc 6.6 changelog does not mention its removal.

1 1

Vectors and Matrices
by dBuchmann＠gmx.net 06 Nov '06

06 Nov '06

Is there a library implementing vectors and matrices in a possible elegant manner. Even perhaps with Tensor-/Kronecker-Product and Scalar-Product. greetings. _________________________________ dBuchmann(a)gmx.net; visit http://filzbits.de

2 1

Re: Haskell-Cafe Digest, Vol 39, Issue 6
by Chad Scherrer 06 Nov '06

06 Nov '06

Lemmih wrote: > Using 'seq' is generally a bad idea. It can worsen the performance if > not used carefully and GHCs strictness analyser is usually good > enough. Is GHC.Conc.pseq any better? Usually the whole point of making things more strict is to optimize performance for pieces you know will be evaluated anyway. It's frustrating if there's not a consistent way to do this that works well. Lately, I've been using lots of strictness annotations and bang patterns - are there non-obvious places this could slow things down? Would it be possible for the type system to distinguish at compile time whether something would need to be evaluated, and optimize away redundant `seq`s? Maybe this is what the strictness analyzer does already. Chad

4 4

Module visibility of data type constructors
by Slavomir Kaslev 05 Nov '06

05 Nov '06

Hello. I have a simple question for data type constructors visibility. Take a look: module Foo (Bar) where data Bar = Bar In ghc this allows me to use Bar, the type constructor, in another module, although it shouldn't be visible outside Foo. On the other hand, if I change Bar's definition as: data Bar = Baz Baz isn't visible outside Foo. Is this the correct behavior or is it bug in ghc? Cheers. -- Slavomir Kaslev

3 5

64bit code output is less optimized than 32bit in ghc?
by isto 05 Nov '06

05 Nov '06

Hi again, Still playing with the Mersenne Twister and here is the updated 64 bit version so that there are not so many constructor calls on next64 (together with updated compiling flags). I was wondering why different runs can have such different run times and the cause was found to be my system: also the C version running times can vary (usually 0.65 but sometimes 0.3). The 64 bit version took usually about 1.1 or 1.2 seconds while 32bit version required only 0.78 (against 0.65 with C for both 32 and 64 bit versions). Since the real work horse here is the next64 function, I took a look of Core. There seems to be an extra case-statement in 64bit version and this might explain the performance drop (about 6 or 7 lines below _DEFAULT text on both versions below). Relevant parts of the Core below, code attached. It is very possible that I'm missing something obvious here. So what is happening here? :) Thanks again for any comments! br, Isto -------------------------------------------- Core (32 and 64 nexts) Rec { Mersenne.$wnext64 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64 -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, (GHC.Word.Word64, GHC.Base.Int) #) [GlobalId] [Arity 3 Str: DmdType LLL] Mersenne.$wnext64 = \ (w_s2Zq :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64) (ww_s2Zt :: GHC.Prim.Int#) (w1_s2Zv :: GHC.Prim.State# GHC.Prim.RealWorld) -> case ww_s2Zt of ds_X2F1 { __DEFAULT -> case w_s2Zq of wild_a2Pp { Data.Array.Base.STUArray ds2_a2Pr ds3_a2Ps marr#_a2Pt -> case GHC.Prim.readWord64Array# @ GHC.Prim.RealWorld marr#_a2Pt ds_X2F1 w1_s2Zv of wild2_a2PA { (# s2#_a2PC, e#_a2PD #) -> (# s2#_a2PC, ((case lit_r34C of wild1_a2Ol { GHC.Word.W64# y#_a2On -> let { ww1_a2NY [Just L] :: GHC.Prim.Word# [Str: DmdType] ww1_a2NY = GHC.Prim.xor# e#_a2PD (GHC.Prim.and# (GHC.Prim.uncheckedShiftRL# e#_a2PD 29) __word 6148914691236517205) } in let { ww2_X2Q0 [Just L] :: GHC.Prim.Word# [Str: DmdType] ww2_X2Q0 = GHC.Prim.xor# ww1_a2NY (GHC.Prim.and# (GHC.Prim.uncheckedShiftL# ww1_a2NY 17) __word 8202884508482404352) } in let { ww3_X2QE [Just L] :: GHC.Prim.Word# [Str: DmdType] ww3_X2QE = GHC.Prim.xor# ww2_X2Q0 (GHC.Prim.and# (GHC.Prim.uncheckedShiftL# ww2_X2Q0 37) y#_a2On) } in GHC.Word.W64# (GHC.Prim.xor# ww3_X2QE (GHC.Prim.uncheckedShiftRL# ww3_X2QE 43)) }), (GHC.Base.I# (GHC.Prim.+# ds_X2F1 1))) #) } }; 312 -> case Mersenne.generateNumbers64 w_s2Zq w1_s2Zv of wild_a2DL { (# new_s_a2DN, a87_a2DO #) -> case Mersenne.$wnext64 w_s2Zq 0 new_s_a2DN of wild1_X2Fy { (# new_s1_X2FB, a871_X2FD #) -> case a871_X2FD of wild2_Xar { (w2_aU2, iN_aU3) -> (# new_s1_X2FB, wild2_Xar #) } } } } end Rec } Mersenne.next64 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64 -> GHC.Base.Int -> GHC.IOBase.IO (GHC.Word.Word64, GHC.Base.Int) [GlobalId] [Arity 3 Worker Mersenne.$wnext64 Str: DmdType LU(L)L] Mersenne.next64 = __inline_me (\ (w_s2Zq :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64) (w1_s2Zr :: GHC.Base.Int) (w2_s2Zv :: GHC.Prim.State# GHC.Prim.RealWorld) -> case w1_s2Zr of w3_X30R { GHC.Base.I# ww_s2Zt -> Mersenne.$wnext64 w_s2Zq ww_s2Zt w2_s2Zv }) Rec { Mersenne.$wnext32 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32 -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, (GHC.Word.Word32, GHC.Base.Int) #) [GlobalId] [Arity 3 NoCafRefs Str: DmdType LLL] Mersenne.$wnext32 = \ (w_s2YJ :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32) (ww_s2YM :: GHC.Prim.Int#) (w1_s2YO :: GHC.Prim.State# GHC.Prim.RealWorld) -> case ww_s2YM of ds_X2CS { __DEFAULT -> case w_s2YJ of wild_a2Hd { Data.Array.Base.STUArray ds2_a2Hf ds3_a2Hj marr#_a2Hk -> case GHC.Prim.readWord32Array# @ GHC.Prim.RealWorld marr#_a2Hk ds_X2CS w1_s2YO of wild2_a2Hr { (# s2#_a2Ht, e#_a2Hu #) -> (# s2#_a2Ht, ((let { ww1_a2Fr [Just L] :: GHC.Prim.Word# [Str: DmdType] ww1_a2Fr = GHC.Prim.xor# e#_a2Hu (GHC.Prim.uncheckedShiftRL# e#_a2Hu 11) } in let { ww2_X2GX [Just L] :: GHC.Prim.Word# [Str: DmdType] ww2_X2GX = GHC.Prim.xor# ww1_a2Fr (GHC.Prim.and# (GHC.Prim.narrow32Word# (GHC.Prim.uncheckedShiftL# ww1_a2Fr 7)) __word 2636928640) } in let { ww3_X2Hp [Just L] :: GHC.Prim.Word# [Str: DmdType] ww3_X2Hp = GHC.Prim.xor# ww2_X2GX (GHC.Prim.and# (GHC.Prim.narrow32Word# (GHC.Prim.uncheckedShiftL# ww2_X2GX 15)) __word 4022730752) } in GHC.Word.W32# (GHC.Prim.xor# ww3_X2Hp (GHC.Prim.uncheckedShiftRL# ww3_X2Hp 18))), (GHC.Base.I# (GHC.Prim.+# ds_X2CS 1))) #) } }; 624 -> case Mersenne.generateNumbers32 w_s2YJ w1_s2YO of wild_a2DL { (# new_s_a2DN, a87_a2DO #) -> case Mersenne.$wnext32 w_s2YJ 0 new_s_a2DN of wild1_X2F2 { (# new_s1_X2F5, a871_X2F7 #) -> case a871_X2F7 of wild2_X80 { (w2_aSH, iN_aSI) -> (# new_s1_X2F5, wild2_X80 #) } } } } end Rec } Mersenne.next32 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32 -> GHC.Base.Int -> GHC.IOBase.IO (GHC.Word.Word32, GHC.Base.Int) [GlobalId] [Arity 3 Worker Mersenne.$wnext32 NoCafRefs Str: DmdType LU(L)L] Mersenne.next32 = __inline_me (\ (w_s2YJ :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32) (w1_s2YK :: GHC.Base.Int) (w2_s2YO :: GHC.Prim.State# GHC.Prim.RealWorld) -> case w1_s2YK of w3_X2ZO { GHC.Base.I# ww_s2YM -> Mersenne.$wnext32 w_s2YJ ww_s2YM w2_s2YO })

1 0

Unicode strings
by Pupeno 05 Nov '06

05 Nov '06

Hello, I am trying to make a program that outputs some Unicode characters but the output doesn't match what I try to print. Attached is a little test program. It tries to print the arrows "←↑→↓" but instead it outputs "\220\221\222\223" (that is, character number 220, then 221, then 222). I've also tried writing the Unicode code points (although GHC 6.6 should deal just fine with Unicode source code) and I get the same result. In case anybody wants to try, this would be the string: "\8592\8593\8594\8595". I am also attaching the output file, you can see that the contents are not right. Any ideas what am I doing wrong here ? Thank you. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com)

4 3

A restricted subset of CPP included in a revision of Haskell 98
by Brian Smith 05 Nov '06

05 Nov '06

Hi, I find it strange that right now almost every Haskell program directly or indirectly (through FPTOOLS) depends on CPP, yet there is no effort to replace CPP with something better or standardize its usage in Haskell. According to the following document, and my own limited experience in reading Haskell code, CPP is the most frequently used extension: http://hackage.haskell.org/trac/haskell-prime/wiki/HaskellExtensions I think that if we accepted that CPP was part of the language, we could then place some restrictions on its use to facilitate easier parsing. Here are some suggestions, off the top of my head: * #define can only be used for parameterless definitions * #define'd symbols are only visible to the preprocessor * #define can only give a symbol a value that is a valid preprocessor expression * #define can only appear above the module declaration * a preprocessor symbol, once defined, cannot be undefined or redefined * #include and #undef are prohibited * The preprocessor can only be used at the top level. In particular, a prepropcessor conditional, #error, #warn, #line would not be allowed within the export list or within a top-level binding. * A Haskell program must assume that any top-level symbol definitions are constant over the entire program. For example, a program must not depend on having one module compiled with one set of command-line preprocessor symbol bindings and another module defined with a different set of bindings. * preprocessor directives must obey Haskell's layout rules. For example, an #if cannot be indented more than the bindings it contains. The result would be: * Syntax can be fully checked without knowing the values of any preprocessor symbols. * Preprocessor syntax can be added easily to a Haskell parser's BNF description of Haskell. * No tool will need to support per-file/module preprocessor symbol bindings. Again, all this is just off the top of my head. I am curious about what problems these restrictions might cause, especially for existing programs. I know that GHC itself uses some features that would be prohibited here. But, GHC is really difficult for tools to handle even with these restrictions on its source code. For now, I am more interested in the libraries in FPTOOLS and users' programs. What libraries/programs cannot easily be reorganizated to meet these restrictions? I suspect "#define'd symbols are only visible to the preprocessor" would be the most troublesome one. Thanks, Brian

7 9