May 2006 - Haskell-Cafe

Creating static libraries using GHC
by Tom Hawkins 17 Mar '07

17 Mar '07

I have a chunk of Haskell code I would like wrap up and distribute as a library. Is there a way to build a static library (*.a) that includes my code plus the Haskell runtime, which C programs can easily link against? Here is what I have tried so far... ghc --make -fffi MyLib # Builds MyLib.o and MyLib_stub.o. gcc -c -I/usr/local/lib/ghc-6.4.1/include MyLibWrapper.c ar -r libMyLib.a MyLib.o MyLib_stub.o MyLibWrapper.o This works fine when I use ghc to compile and link a C program... ghc main.c libMyLib.a But if I use gcc, it throws a lot of unresolved references. I have no problem compiling with ghc, but the folks using my library probably won't have it installed. I added -v to ghc to see how it calls gcc; it seems to link in different libraries based on what Haskell libraries are being used, and it undefines a bunch is symbol references. Are there any switches to have ghc return a single archive with everything included? Please excuse my ignorance of the linking process. Thanks for any help! -Tom

3 2

Editors for Haskell
by Walter Potter 08 Jun '06

08 Jun '06

All, I hope that this is the right place for this question. I'm using Haskell (GHC and Hugs) on several different platforms. Windows, OS X and Linux systems. I'd like to have an IDE that works well for medium to large size projects. I know of Eclipse and hIDE. Vim works fine but I'd like more. hiDE seems to be "in process." What would you suggest? I'll be asking my students to use the same IDE. Thanks, Walt

16 22

Polymorphic Sudoku solver
by Chris Kuklewicz 08 Jun '06

08 Jun '06

A while back there was a long thread about Sudoku solvers (some of which ended up on http://haskell.org/haskellwiki/Sudoku ). I contributed my brute-force dancing links solver at the time, and mentioned that I had a by-logic solver that, while a bit slow, was as good as most of those being discussed. At the time the code for my solver was too ugly to post. Attached is a cleaned up version. I have gone back and rewritten it, and come to the conclusion: There are only two deduction algorithms: "subsets" and "blocks". These subsume the other types of propagation and deduction. So I made this version as a "minimalist" example instead of going for performance. The "subsets" algorithm can be applied to all 6 permutations of row column and value, as well as 1 special case of value and block indices. The "blocks" algorithm can be applied 4 ways (in two flavors and to either permutation of row/column or column/row). There are newtypes for row, column, value, block index, and sub-block index. The state is held in an array of type DiffArray (R,C,V) Bool The actual computation is a series of concat/map/filter/group/sort operations on the assocs's of the array. The choice of which permutation is handled by leaning on the type system to reify the type into appropriate view,shuffle, and unshuffle functions. It should solve exactly the same number of puzzles as my older version, where "I sent the 36628 line sudoku17 puzzle through it and it could solve 31322 of the puzzles, leaving 5306 resistant." -- Chris Kuklewicz module Main (main) where import Data.Ix(inRange,range) import Data.Char(intToDigit,digitToInt) import Deduce(deduce,lo,hi) loC = intToDigit lo hiC = intToDigit hi unsetC = pred loC main = do all <- getContents let puzzles = zip [1..] (map parseBoard (lines all)) act (i,p) = do p' <- deduce p return (i,length p,length p') mapM_ (\ip -> act ip >>= print) puzzles parseBoard :: String -> [(Int,Int,Int)] parseBoard s = map toHint justSet where rcs = [ (r,c) | r <- range (lo,hi), c <- range (lo,hi) ] isHint vC = inRange (loC,hiC) vC justSet = filter (isHint . snd) (zip rcs s) toHint ((r,c),vC) = (r,c,digitToInt vC) {- By Chris Kuklewicz <haskell(a)list.mightyreason.com> -} module Deduce (deduce,lo,hi) where {- The exposed function deduce takes a list of (row,column,value) tuples that are the known parts of the solutions and returns a (hopefully longer) list in the same format. The indices can be any enumerated type in the range (lo,hi). -} import Data.Array.Diff (assocs,(!),(//),ixmap,range,inRange,accumArray,DiffArray,Ix) import Data.List(sortBy,groupBy,transpose,(\\)) import Control.Monad(liftM,guard) default () -- Typesafe values for indices -- This machinery allows for more type safety than if R,C,V,B,D were all Int or Char type E = Int newtype R = R E deriving (Eq,Ord,Ix,Enum,Show) -- Row index newtype C = C E deriving (Eq,Ord,Ix,Enum,Show) -- Column index newtype V = V E deriving (Eq,Ord,Ix,Enum,Show) -- Value index newtype B = B E deriving (Eq,Ord,Ix,Enum,Show) -- 3x3 Block index newtype D = D E deriving (Eq,Ord,Ix,Enum,Show) -- Inside 3x3 Block index lo,hi :: (Enum a) => a lo = toEnum 1 hi = toEnum 9 fullRange :: (Enum a,Ix a) => [a] fullRange = range (lo,hi) rcToBD (R r) (C c) = let (rq,rm) = quotRem (r-lo) 3 (cq,cm) = quotRem (c-lo) 3 b = lo + ( 3*rq + cq ) d = lo + ( 3*rm + cm ) in (B b, D d) bdToRC (B b) (D d) = let (bq,bm) = quotRem (b-lo) 3 (dq,dm) = quotRem (d-lo) 3 r = lo + ( 3*bq + dq ) c = lo + ( 3*bm + dm ) in (R r, C c) -- Typeclasses and Data for "shuffle" and "unshuffle" class (Show x, Ix x, Enum x, Ord x) => IE x instance IE R; instance IE C; instance IE V; instance IE B; instance IE D data Perms a b c = Perms { shuffle' :: (R,C,V) -> (a,b,c) , unshuffle' :: (a,b,c) -> (R,C,V) } -- Reify the types "a b c" to a value of type Perms class (IE a, IE b, IE c) => Perm a b c where perm :: Perms a b c instance Perm R C V where perm = Perms id id instance Perm R V C where perm = Perms (\ (r,c,v) -> (r,v,c)) (\ (r,v,c) -> (r,c,v)) instance Perm C V R where perm = Perms (\ (r,c,v) -> (c,v,r)) (\ (c,v,r) -> (r,c,v)) instance Perm C R V where perm = Perms (\ (r,c,v) -> (c,r,v)) (\ (c,r,v) -> (r,c,v)) instance Perm V R C where perm = Perms (\ (r,c,v) -> (v,r,c)) (\ (v,r,c) -> (r,c,v)) instance Perm V C R where perm = Perms (\ (r,c,v) -> (v,c,r)) (\ (v,c,r) -> (r,c,v)) -- Special cases instance Perm B D V where perm = Perms (\ (r,c,v) -> let (b,d) = rcToBD r c in (b,d,v)) (\ (b,d,v) -> let (r,c) = bdToRC b d in (r,c,v)) instance Perm V B D where perm = Perms (\ (r,c,v) -> let (b,d) = rcToBD r c in (v,b,d)) (\ (v,b,d) -> let (r,c) = bdToRC b d in (r,c,v)) shuffle :: (Perm a b c) => (R,C,V) -> (a,b,c) shuffle = shuffle' perm unshuffle :: (Perm a b c) => (a,b,c) -> (R,C,V) unshuffle = unshuffle' perm -- Array types, values and functions type Index = (R,C,V) type Cell = Bool on,off :: Cell on = True -- Means this might be part of the solution off = False -- Means this cannot be part of the solution boundsCube :: (Perm a b c) => ((a,b,c),(a,b,c)) boundsCube = ((lo,lo,lo),(hi,hi,hi)) type Cube = DiffArray Index Cell emptyCube :: Cube emptyCube = accumArray const on boundsCube [] type View a b c = DiffArray (a,b,c) Cell {-# INLINE view #-} view :: (Perm a b c) => Cube -> View a b c view cube = ixmap boundsCube unshuffle cube type Hints = [(Index,Cell)] isOn :: (Perm a b c) => View a b c -> [(a,b,c)] isOn = map fst . filter snd . assocs -- The goal is to create functions that turn the current Cube into a -- list of Hints. These Hints will be purely subtractive: they all -- turn a Cell from 'on' to 'off'. type Rule = Cube -> Hints -- Small utility functions fst3 (x,_,_) = x; snd3 (_,x,_) = x; thd3 (_,_,x) = x fst4 (x,_,_,_) = x; snd4 (_,x,_,_) = x; thd4 (_,_,x,_) = x; fth4 (_,_,_,x) = x by un bi = (\ left right -> (un left) `bi` (un right)) sortWith un = sortBy (by un compare) groupWith un = groupBy (by un (==)) groupSort un = groupWith un . sortWith un atLeastOne = not . null atLeastTwo (_:_:_) = True; atLeastTwo _ = False exactlyOne [_] = True; exactlyOne _ = False oneOrTwo [_] = True; oneOrTwo [_,_] = True; oneOrTwo _ = False {- ruleBlock1 : When operating on Perm V R C: Given a value V, look along each row and see which blocks that value may occupy. Find a row R1 for which the value is allowed in exactly one block B1 (an no other blocks). This occupies [(B1,d)] in B1. Eliminate V from the other locations in B1. Given a value V, look along each row and see which blocks that value may occupy. Find two rows [R1,R2] for which the value only is allowed in exactly the same two blocks [B1,B2] (and no others). These occupy [(B1,d11s)] in R1, [(B2,d12s)] in R1, [(B1,d21s)] in R2, and [(B2,d22s)] in R2. Eliminate V from the other locations in B1 and the other locations in B2. Works for R and C reversed, of course. -} {- ruleBlock2 : When operating on Perm V R C: Given a value V, look inside each block and see which rows that value may occupy. Find a block B1 for which only one row R1 is occupied (and no other rows). This occupies [(R1,c11s)] in B1. Eliminate V from all the other c's in row R1. Given a value V, look inside each block and see which rows that value may occupy. Find two blocks [B1,B2] for which the value only is allowed in exactly the same two rows [R1,R2] (and no others). These occupy [(R1,c11s)] in B1, [(R1,c12s)] in B2, [(R2,c21s)] in B1, and [(R2,c22s)] in B2 for some C's. Eliminate V from the other rows in R1 and the other columns in R2. Works for R and C reversed, of course. -} {- ruleBlockP There is enough similarity between ruleBlock1 and ruleBlock2 to parameterize over expand and contract. The V index is special because it is "orthogonal" to the 3x3 blocks. The line sVsA2 = map (filter atLeastTwo) $ sVsA -- drop unique ones is used to prevent propagating solved constraints, as rule4P should already do this in its k==1 case. (assocs view) becomes useful hints through a chain of map, sort, group, filter, and concat operations. The assemble function also takes care to remove redundant hints by consulting the view. -} {-# INLINE ruleBlockP #-} ruleBlockP :: forall a b c x y . (IE a, IE b, IE c, Perm V x y) => ( (V,x,y) -> (V,a,b,c) ) -- "expand" -> (V -> b -> [c] -> [Index]) -- "contract" -> View V x y -> Hints ruleBlockP expand contract view = let allOn :: [(V,a,b,c)] allOn = map expand . isOn $ view sV :: [ [(V,a,b,c)] ] sV = groupWith fst4 $ allOn -- group by V sVsA :: [[ [(V,a,b,c)] ]] sVsA = map (groupSort snd4) $ sV -- group by a sVsAsB,sVsAsB2 :: [[[ [(V,a,b,c)] ]]] sVsAsB = map (map (groupSort thd4)) $ sVsA -- group by b -- These filters are to remove empty and redundantly full possibilities sVsAsB2 = filter atLeastOne . map (filter oneOrTwo) $ sVsAsB sVsAsBgB :: [[ ([b],[[(V,a,b,c)]]) ]] -- The filter is to remove solved parts of the puzzle (punt to ruleSubsetP) sVsAsBgB = map (map getAllB . filter (atLeastTwo . concat)) $ sVsAsB2 where getAllB :: [[(V,a,b,c)]] -> ([b],[[(V,a,b,c)]]) getAllB vabcss = (map (thd4 . head) vabcss, vabcss) -- length (concat vabcss) >= 2 useful :: [ [([b],[[(V,a,b,c)]])] ] useful = concatMap (filter exactlySame . groupSort fst) $ sVsAsBgB where exactlySame :: [([b],[[(V,a,b,c)]])] -> Bool exactlySame sas@((sbs,_):_) = length sas == length sbs assemble :: [ ([b],[[(V,a,b,c)]]) ] -> Hints assemble stuff = [ (rcv,off) | rcv <- ixs, (view ! shuffle rcv) /= off ] where byVB :: [[(V,a,b,c)]] byVB = map concat . transpose . map snd $ stuff -- Regroup by identical 'b' -- byVB = groupSort thd4 . concat . concat . map snd $ stuff -- equivalent act :: [(V,a,b,c)] -> [Index] act allVB@((v,_,b,_):_) = contract v b (fullRange \\ map fth4 allVB) ixs :: [Index] ixs = concatMap act byVB in concatMap assemble useful {-# INLINE ruleBlock1 #-} ruleBlock1 :: (Perm V x y) => View V x y -> Hints ruleBlock1 = ruleBlockP expand contract where expand all@(v,x,y) = let (r,c,_) = unshuffle all (b,d) = rcToBD r c in (v,x,b,d) contract v b ds = map undo ds where undo d = let (r,c) = bdToRC b d in (r,c,v) {-# INLINE ruleBlock2 #-} ruleBlock2 :: (Perm V x y) => View V x y -> Hints ruleBlock2 = ruleBlockP expand contract where expand all@(v,x,y) = let (r,c,_) = unshuffle all (b,_) = rcToBD r c in (v,b,x,y) contract v x ys = map undo ys where undo y = unshuffle (v,x,y) ruleBlocks :: [Rule] ruleBlocks = [ (\ known -> ruleBlock1 (view known :: View V R C) ) , (\ known -> ruleBlock1 (view known :: View V C R) ) , (\ known -> ruleBlock2 (view known :: View V R C) ) , (\ known -> ruleBlock2 (view known :: View V C R) ) ] {- Given a list of locations, such as for the 9 columns of a row, look at the allowed values at each location. Find a subset of k columns for which the union of their allowed values [V..] has length k. Then eliminate [V..] from the (9-k) other columns. This clearly finds a list of N columns each with the same N values if such a thing exists, so it subsumes rule1P. This is fully symmetric in R C and V and depends on the constaints in R and V but not C. So the (View B D V) case also works. A useful property of this rule is that once there is only one way to place a value in a row or column or block then it will propagate that solution to the related contraints. This is the case when minK is 1. -} {-# INLINE ruleSubsetP #-} ruleSubsetP :: forall a b c.(Perm a b c) => View a b c -> Hints ruleSubsetP view = let allOn :: [(a,b,c)] allOn = isOn $ view sAsB :: [[ [(a,b,c)] ]] sAsB = map (groupWith snd3) . groupWith fst3 $ allOn sAsBgC :: [ [(Int,[c],[(a,b,c)])] ] sAsBgC = map (sortWith fst3 . map (\ abcs -> (length abcs ,map thd3 abcs ,abcs) ) ) $ sAsB makeChains :: [(Int,[c],[(a,b,c)])] -> Int -> [(a,[b],[c])] makeChains input k = filter check . map toChain . subsets k . upToK $ input where upToK :: [(Int,[c],[(a,b,c)])] -> [(Int,[c],[(a,b,c)])] upToK = takeWhile ((k>=).fst3) toChain :: [(Int,[c],[(a,b,c)])] -> (a,[b],[c]) toChain vals = ( fst3 . head . thd3 . head $ vals -- record "a" for easy retrieval later , map (snd3 . head . thd3) $ vals -- the bs, length [b] == length vals == k by property of subsets k , combine . map snd3 $ vals) -- union of the cs at each b in bs check :: (a,[b],[c]) -> Bool check (_,_,cs) = (k == length cs) -- check that length [c] == k as well getUseful :: [(Int,[c],[(a,b,c)])] -> [(a,[b],[c])] getUseful [] = [] getUseful input = concatMap (makeChains input) [minK .. maxK] -- assertion: (length input) == (length . combine . map snd3 $ input) where minK,maxK :: Int minK = fst3 . head $ input maxK = pred . length $ input useful :: [(a,[b],[c])] useful = concatMap getUseful sAsBgC {- The chains are (a,bs,cs) such that cs == nub . sort $ [ z | (x,y,z) <- allOn, x==a, y `elem` bs] and length bs == length cs. Thus all the (a,b in bs,c) in the final puzzle have distict c in cs. For location (a,b' not in bs,c') cannot have c' in cs, thus if c' is in cs then (a,b',c') should be turned off. -} assemble :: (a,[b],[c]) -> Hints assemble (a,inBs,inCs) = do -- List Monad b <- fullRange \\ inBs c <- inCs let abc :: (a,b,c) abc = (a,b,c) guard (view ! abc) return (unshuffle abc,off) in concatMap assemble useful -- All subsets of length 'k', order is stable subsets :: Int -> [a] -> [[a]] subsets 0 _ = [[]] subsets _ [] = [] subsets k (x:xs) = (fmap (x:) (subsets (pred k) xs)) ++ subsets k (xs) -- Hopefully efficient merge of (list of (sorted lists)), unique values only combine :: (Ord a) => [[a]] -> [a] combine [] = [] combine [x] = x combine xs = let (a,b) = split xs in merge (combine a) (combine b) where split [] = ([],[]) split [a] = ([a],[]) split (x:y:cs) = let (a,b) = split cs in (x:a,y:b) merge a [] = a merge [] b = b merge a@(x:a') b@(y:b') = case compare x y of EQ -> x : merge a' b' LT -> x : merge a' b GT -> y : merge a b' {-# INLINE eachPerm #-} eachPerm :: (forall x y z. (Perm x y z) => View x y z -> Hints) -> [ Rule ] eachPerm rule = [ (\ known -> rule ( view known :: View R C V ) ) , (\ known -> rule ( view known :: View R V C ) ) , (\ known -> rule ( view known :: View C V R ) ) , (\ known -> rule ( view known :: View C R V ) ) , (\ known -> rule ( view known :: View V R C ) ) , (\ known -> rule ( view known :: View V C R ) ) ] ruleSubsets :: [ Rule ] ruleSubsets = eachPerm ruleSubsetP ++ [ (\ known -> ruleSubsetP (view known :: View B D V) ) ] allRules :: [ Rule ] allRules = ruleSubsets ++ ruleBlocks -- Applying the rules {- The evolution strategy is simple: Apply each rule in turn, keeping track whether or not there were any changes. If all rules cause no change then it is done evolving. -} evolve :: Cube -> Cube evolve cube = let (cube',changed) = foldl step (cube,False) allRules in if changed then evolve cube' else cube' where step orig@(known,_) rule = case rule known of [] -> orig hints -> (known // hints,True) toCube :: (Monad m,Enum e) => [(e,e,e)] -> m Cube toCube locs = do hints <- liftM concat $ mapM setLoc locs return (emptyCube // hints) where setLoc:: (Enum e,Monad m) => (e,e,e) -> m Hints setLoc i@(re,ce,ve) = mapM checkM (rs ++ cs ++ vs) where r = toEnum $ fromEnum re c = toEnum $ fromEnum ce v = toEnum $ fromEnum ve rs = [((r',c,v),off) | r' <- fullRange, r' /= r] cs = [((r,c',v),off) | c' <- fullRange, c' /= c] vs = [((r,c,v'),off) | v' <- fullRange, v' /= v] checkM hint = if check hint then return hint else fail "Input location is out of range" check ((r,c,v),_) = and [ inRange (lo,hi) r , inRange (lo,hi) c , inRange (lo,hi) v ] fromCube :: (Enum e) => Cube -> [(e,e,e)] fromCube cube = map head . filter exactlyOne $ [ [ eee | v <- fullRange, cube ! (r,c,v) , let eee = (toEnum $ fromEnum r ,toEnum $ fromEnum c ,toEnum $ fromEnum v) ] | r <- fullRange, c <- fullRange ] consistent :: Cube -> Bool consistent known = and [ consistentView ( view known :: View R C V ) , consistentView ( view known :: View C V R ) , consistentView ( view known :: View R V C ) , consistentView ( view known :: View V B D ) ] where consistentView :: (Perm a b c) => View a b c -> Bool consistentView view = and [ atLeastOne [ () | c <- fullRange, view ! (a,b,c) ] | a <- fullRange, b <- fullRange ] checkCube :: (Monad m) => String -> Cube -> m Cube checkCube msg cube = if consistent cube then return cube else fail msg deduce :: (Monad m,Enum e) => [(e,e,e)] -> m [(e,e,e)] deduce locs = toCube locs >>= checkCube "Inconsistent locations passed in" >>= return . evolve >>= checkCube "Inconsistent cube deduced from input" >>= return . fromCube test :: [(E,E,E)] test = [(1,8,1),(1,9,2),(2,5,3),(2,6,5),(3,4,6),(3,8,7),(4,1,7),(4,7,3),(5,4,4),(5,7,8),(6,1,1),(7,4,1),(7,5,2),(8,2,8),(8,8,4),(9,2,5),(9,7,6)] testC :: IO Cube testC = toCube test check :: IO () check = do c <- testC print (consistent (evolve c))

2 1

Re[2]: [Haskell] My summer of code project: HsJudy
by Bulat Ziganshin 01 Jun '06

01 Jun '06

(moved to haskell-cafe) Hello Jean-Philippe, Tuesday, May 30, 2006, 2:58:01 PM, you wrote: >> you should also see to the Collections package: >> darcs get --partial http://darcs.haskell.org/packages/collections/ >> although it contains only _immutable_ datastructures at this >> moment. may be, you can codevelop with Bernardy interface for mutable >> maps/sets > I'm not sure there is significant overlap between what we're doing. > I'd be delighted to cooperate if you think this is possible though. well, what i think: while all the actual work will be performed by Caio himself, we can help him (and to ourselves as possible future users of this lib) by describing infrastructure in that he need to insert his work and pointing to "adjancent" projects so, Caio, now i write for you, better organizing my previous post: 1. In terms of Haskell, Judy is a library of _mutable_ collections of _unboxed_ elements. i pointed you to the Array wiki page, where differences between boxed and unboxed, mutable and immutable datastructures are described 2. Collections is a library of _immutable_ datastructures, and Jean-Philippe especially omitted any support for mutable datastructures - because it's the whole story of it's own. So, you don't need to write your work as part of the Collections library 3. Nevertheless, Collections has GREAT organization and it will be very helpful to study it. in particular, see at the Data.Collections module, what describes various classes into which all collections are fitted, and hierarchy between them 4. Next, when you will search for the datatypes/classes whose interface you can imitate, you will find only Data.HashTable - other datatypes in standard libraries are either immutable (say, Map) or need contiguous indexes (say, MArray). So you will need to create your own interface and here you can borrow from the Collections lib. Just see at the differences between IArray and MArray classes. They are very close, only MArray class update arrays on-the-place and has additional 'Monad m' on all it's return types. say, class IArray a e where unsafeAt :: (Index i) => a i e -> i -> e becomes class MArray a e m where unsafeRead :: (Index i) => a i e -> i -> m e You can do the same with Collections classes. instead of reinventing the wheel, you can add letter 'M' to it :) say, class Monoid c => Map c k a | c -> k a where insert :: k -> a -> c -> c delete :: k -> c -> c member :: k -> c -> Bool would become class (Monoid c, Monad m) => MapM c k a | c -> k a where insertM :: k -> a -> c -> m () deleteM :: k -> c -> m () memberM :: k -> c -> m Bool 5. as i already said, then you should use StablePtr and any form of hashing/seriazliation in order to map between boxed (Haskell) and unboxed (C) values. and then you can develop series of Diff transformers what emulates immutable collections via mutable ones (say interface of class Map via the interface of class MapM), DiffArray can serve as template here 6. There is no class framework for container types other than this Data.Collections module, so implementing it's close imitation (with monadic operations) will help future users to easily learn and use both interfaces -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 4

Re: [Haskell] installing streams library
by Chad Scherrer 01 Jun '06

01 Jun '06

On 5/20/06, Donald Bruce Stewart <dons(a)cse.unsw.edu.au> wrote: > > > Data.ByteString is in the base libraries now. > For a bit of the flavour, see: > http://haskell.org/haskellwiki/Wc > In this message http://article.gmane.org/gmane.comp.lang.haskell.general/13625 Bulat says, i foresee that Streams + Fast Packed Strings together will yield a breakthrough in GHC I/O speed, and this can be implemented even without waiting for GHC 6.6 Before reading this I had thought it might be an XOR situation, but now it seems a happy coexistence may be possible. Are there any preliminary results on how these might work together, and the potential speedups? -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

8 20

Re: [Haskell-cafe] Editors for Haskell
by Doaitse Swierstra 01 Jun '06

01 Jun '06

On 2006 mei 30, at 17:33, Brian Hulley wrote: > But the buffer will nearly always be incomplete as you're editing it. > > I was kind of hoping that the syntax of Haskell could be changed so > that for > any sequence of characters there would be a unique parse that had a > minimum > number of "gaps" inserted by the editor to create a complete parse > tree, and > moreover that this parse could be found by deterministic LL1 recursive > descent. If you use my parsercombinators, and are willing to work on the grammar I think this can in principle be done. The combinators automatically "correct" incorrect (i.e. in this case incomplete) input, but: - you may really need some time to tune the grammar so the corrections are what a user might expect (there are many hooks for doing so, but it will takje some effort, since this s also a human interface issue) - making a Haskell grammar that parsers top-down is not an easy task, and making it LL1 is definitely impossible, but also not needed if you use my combinators - we could in principle provide you with a complete parser for Haskell using our combinators that was tested by replacing the GHC parser with this parser, and that worked (contact athurb(a)cs.uu.nl to get a copy of his code) - did you think about how to handle the offside rule? If not, the good news is that we have combinators for that too. Doaitse Swierstra > > Haskell already seems so very close to having this property - its a > real > pity about => Not only the =>, but e.g. the commonality between patterns and expressions makes left factorisation a not so simple task. > > The problem is: when Haskell was designed, no one seems to have > thought > about the syntax from the point of view of making it easy to parse or > ensuring that it would have this nice property for editing. > >> >>> foo :: {SomeClass a} a->a >>> a Prelude.+ b -- no spaces in the qvarsym >>> a `Prelude.(+)` b -- a little generalization >>> a `Prelude.(+) b -- no need for closing ` >> >> I would not like an editor that forces me to use a special coding >> style (like using brackets where not strictly necessary). Even less >> would I like to use one that introduces non-standard syntax. >> >> My humble opinion is that you'll have to bite the bullet and >> implement >> your syntax recognizer so that it conforms to Haskell'98 (including >> the approved addenda) [and addtionally however many of the existing >> extensions you'll manage to support]. It may be more difficult but in >> the end will also be a lot more useful. And you'll have to find a way >> to (unobtrusively!) let the user know whether some piece of code does >> not yet have enough context to parse it unambigously. > > Thanks for the feedback - I suppose I was being overly optimistic > to think I > could just change the language to suit my editor ;-). > I'll have to find a balance between what I'm able to implement and > what is > specified in Haskell98 (or Haskell' etc) - just as GHCi has done with > qvarsym, and perhaps have different levels of conformance to H98 so > people > could choose their preferred balance between conformity and > instantaneousness of feedback (everything would of course still be > loaded/saved as H98). > > Regards, Brian. > > -- > Logic empowers us and Love gives us purpose. > Yet still phantoms restless for eras long past, > congealed in the present in unthought forms, > strive mightily unseen to destroy us. > > http://www.metamilk.com > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Newbie: Applying Unknown Number Arguments to A Partial Function
by Aditya Siram 31 May '06

31 May '06

I am trying to write a function 'applyArguments' which takes a function and a list and recursively uses element each in the list as an argument to the function. I want to do this for any function taking any number of arguments. applyArgument f (arg) = f arg applyArgument f (arg:args) = applyArgument (f arg) args This has failed in Hugs, so my question is: Can I conceptually do this? If so, what is the type signature of this function? Deech

8 9

changing out
by Jenny678 31 May '06

31 May '06

hello, i want to change my input integers In> 23 98 Out> 98 23 I think its simple... sorry .... my first steps in Haskell.... thanks for solutions. -- View this message in context: http://www.nabble.com/changing+out-t1707014.html#a4634189 Sent from the Haskell - Haskell-Cafe forum at Nabble.com.

2 1

String to binary tree
by Nuno Santos 31 May '06

31 May '06

Hi, I have this type which represents polish expressions (floorplan representation): data PeAux a = Folha Char | Nodo Char (PeAux a) (PeAux a) deriving Show The reverse polish expression are the result of doing a post order visit to the tree One example of this reverse polish expression is "12H3V" and a example of tree is pe5 = Node 'V' (Node 'H' (Folha '1') (Folha '2')) (Folha '3') the tree above is the same as the expression "12H3V" What i need and i cant do is turn the expression a tree again... I have done the following: converteAux [] (x,y) = (x,y) converteAux (a:t) (x,y) | ((length (a:t))<3) = converteAux [] (x,y ++ (a:t)) converteAux (a:b:t) (x,y) | ((length (a:b:t))<3) = converteAux [] (x,y ++ (a:b:t)) converteAux (a:b:c:t) (x,y) | (isNumber a) && (isNumber b) && (isLetter c) = converteAux t (x ++ [(Nodo c (Folha a) (Folha b))],y) | otherwise = converteAux (b:c:t) (x,y++[a]) The strategy followed is to recognize operand, operand, operator and then put it as a basic element in a list, for instance, 12H -> Node 'H' (Folha '1') (Folha '2') And at the end put it togheter in one tree. ( not done yet) But i'm getting to the conclusion that it doesnt cover every case... Can anybody give me a light here? Many thx, Best regards, Nuno Santos

4 5

On GADT, phantom types, etc. terminology
by oleg＠pobox.com 30 May '06

30 May '06

David Roundy wrote: > data CommuteResult a b c where > CR :: C a b c d => (P a d, P d c) -> CommuteResult a b c > ... > or that somehow GADTs aren't interacting with FDs as I'd like It must be emphasized that there are *NO* GADTs is the above code. Except Stefan Monnier's message, no code posted in the thread `help with MPTC for type proofs?' had any GADTs, the notation |data ... where| notwithstanding. In particular, the data type |CommuteResult a b c| is the ordinary algebraic datatype, and can be written in the traditional notation as > data CommuteResult a b c = forall d. C a b c d => CR (P a d, P d c) To recall, the datatype > data MEither a b where > MLeft :: a -> MEither a b > MRight :: b -> MEither a b is the ordinary algebraic datatype > data MEither a b = MLeft a | MRight b The two notations are totally equivalent. The constructors MLeft and MRight create the values of the type |MEither a b| -- which is just as general as the type being defined |MEither a b|. OTH, > data MEither2 a b where > MLeft2 :: Int -> MEither2 Int b > MRight2 :: b -> MEither2 Char b is truly _generalized_ ADT, because the values created by the constructors MLeft2 and MRight2 have the types that span only the subset of the type family |MEither2 a b|. Thus, to tell if something written in the |data ... where| notation is GADT or not, we just look at the result type. If it is the same as what follows the |data| keyword, we have the ordinary ADT. Incidentally, I strongly prefer writing ordinary algebraic data types in the traditional notation (precisely to avoid the confusion with GADTs and to keep the code portable). Because David Roundy's example had no GADTs, it is not fair to blame GADT's interacting with FD. There are indeed issues, at present, with GADT and FD. But those issues do not bear on the problem at hand. Therefore, waiting for GHC 6.8 is, alas, hopeless in this respect. David Roundy wrote: > I want the return type "d" to be a phantom type of some sort (although > I'm not clear on the distinction between phantom and existential > types). Well, they are, in a sense, dual to each other. In the declaration, > data Patch a b = P a the type variable 'b' appears only on the left-hand side of the definition. The corresponding type is phantom. In the declaration > data PatchW a = forall b. PW (Patch a b) the type variable 'b' appears only on the right-hand side of the defining equation. So, informally, the type |PatchW a| is existential, abstracting over |b|. Perhaps the |where| notation makes things clearer: > data Patch a b where P :: a -> Patch a b > data PatchW a where PW :: Patch a b -> PatchW a Here, the type variable |b| shows up only in the result of |P|. It is phantom. The type variable |b| shows up only in the argument of |PW|. It is existential. David Roundy wrote: > when I realized that the problem could be solved much more elegantly > using GADTs as a type witness (with unsafeCoerce#, admittedly) That is quite puzzling: the whole advantage of GADTs is that we don't need to coerce values because type coercion, after checking the run-time evidence (that is, successful pattern-match) is the very essence of GADTs. Incidentally, to coerce phantom types, there is no need to resort to unsafeCoerce#. The access to the data constructor suffices. David Roundy wrote: > Can someone explain to me why this doesn't work? > > {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-} > > module MPTC where > > > > class C a b c d | a b c -> d, a d c -> b > > > > instance (C a b c d) => C a d c b > > > > data P a b = P deriving (Show) > > > > data CommuteResult a b c where > > CR :: C a b c d => (P a d, P d c) -> CommuteResult a b c When we abstract over |d|, there is generally no way to get the original type back (short of various casts, which generally require run-time evidence). One can think of it as upcast/downcast problem in OO: we can always pretend that an object of the type A is an object of a more general type ASuper (and any object is an object of the Top type). However, downcasting from a value of a more general type to the value of a more specific type requires some run-time evidence (even if the more general value was obtained by the upcast from the desired specific type). The nature of abstraction is to irreversibly forget -- hence the encapsulation guarantee. If that is not desired, we can use some other translucent, type-preserving, ways. For example, > {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-} > module MPTC where > > data P a b = P deriving (Show) > > data CommuteResult a b c = forall d. CR (P a (d b), P (d b) c) > > commute :: (P a (d b), P (d1 b) c) -> CommuteResult a b c > commute (P, P) = CR (P, P) > > test (x,y) = do CR (y',x') <- return $ commute (x,y) > CR (y'', x'') <- return $ commute (x,y) > CR (x''',y''') <- return $ commute (y',x'') > return () which type-checks... David Roundy wrote: > I guess what hasn't been addressed is the question I didn't know to ask... It would help me personally to see the `ideal' code -- the code that you wish to write and to typecheck. The code should be sufficiently realistic (the IO can be stubbed though). I'll be out of town for a week so unable to reply promptly.

2 1