- Haskell-Cafe - Haskell.org

powerset
by Graham Klyne 14 Jun '03

14 Jun '03

A brief search of the libraries didn't reveal (top me) a ready-to-roll powerset function. I thought this may be a useful exercise to see how well I'm picking up on functional programming idioms, so I offer the following for comment: [[ -- |Powerset of a list, in ascending order of size. -- Assumes the supplied list has no duplicate elements. powerSet :: [a] -> [[a]] powerSet as = foldl (++) [] [ combinations n as | n <- intRange 1 (length as) ] -- |Combinations of n elements from a list, each being returned in the -- order that they appear in the list. combinations :: Int -> [a] -> [[a]] combinations _ [] = [] -- Don't include empty combinations combinations n as@(ah:at) | n <= 0 = [[]] | n > length as = [] | n == length as = [as] | otherwise = (map (ah:) $ combinations (n-1) at) ++ (combinations n at) -- |Return list of integers from lo to hi. intRange :: Int -> Int -> [Int] intRange lo hi = take (hi-lo+1) (iterate (+1) 1) -- Tests testcomb0 = combinations 0 "abcd" -- [] testcomb1 = combinations 1 "abcd" -- ["a","b","c","d"] testcomb2 = combinations 2 "abcd" -- ["ab","ac","ad","bc","bd","cd"] testcomb3 = combinations 3 "abcd" -- ["abc","abd","acd","bcd"] testcomb4 = combinations 4 "abcd" -- ["abcd"] testcomb5 = combinations 5 "abcd" -- [] testpower = powerSet "abc" -- ["a","b","c","ab","ac","bc","abc"] ]] I think the recursive use of 'combinations' may be inefficient, and could maybe be improved by "memoizing"? #g ------------------- Graham Klyne <GK(a)NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E

9 21

Green Card and Exceptions
by Matthew Donadio 14 Jun '03

14 Jun '03

Hi all, I have a couple of questions about Green Card and exceptions. I am interfaceing to the GSL to get access to a few functions, and eventually interface all of the special functions to Haskell. And unlike my DSP library, and am trying to get it right the first time. :) Below is a Green Card interface to one of the functions. %fun airy_Ai_e :: Double -> (Double, Double) %call (double x) %code int rc; % double val; % double err; % gsl_sf_result result; % rc = gsl_sf_airy_Ai_e(x, GSL_PREC_DOUBLE, &result); % val = result.val; % err = result.err; %result (double val, double err) This definition works, but it ignores the return code from the library function. The various return codes are from an enum defined in a header file. I would like to throw a Haskell exception (one of the ArithExceptions defined in Control.Exception) depending on the value of "rc". Do I need to create a new DIS for the return values (which are an enum defined in a header), change the function to return a triplet (var,err,rc), and then throw the exception in Haskell land? Is there a way I can do this directly from the GC interface? If I have to create a DIS, can this be shared across several modules that all need the same functionality? Thanks. -- Matthew Donadio (m.p.donadio(a)ieee.org)

2 2

chance to help out on the wiki
by Isaac Jones 13 Jun '03

13 Jun '03

Greetings. We added a page "Fundamental Concepts" to the wiki so that we might have a very specific reference to pass along to people with questions, and to add links to definitions throughout the wiki. http://www.haskell.org/hawiki/FundamentalConcepts A lot of concepts need to be filled in, and if you haven't participated in the Wiki yet, now is a good time :) If you've never used a wiki, you can read about it here: http://www.haskell.org/hawiki/HelpForBeginners You might model your explanations after a page I wrote for PatternMatching which has: - a reference to a tutorial - a reference to the haskell report - an explanation - some examples Feel free to extend and / or correct anything already there. The front page of the wiki is here: http://www.haskell.org/hawiki/FrontPage peace, isaac

1 0

please help
by David Savimbi 13 Jun '03

13 Jun '03

From: David Jonas Savimbi Johannesburg, South Africa Email: djsavimbi(a)phantomemail.com june 13th, 2003. Dear Sir, It is my humble pleasure to write you this letter irrespective of the fact that you do not know me. However, I got your name through your country business directory here in my search for a reliable and trustworthy person that can assist me confidently. My name is Mr.John Jonas Savimbi. I am the son of Late Dr. Jonas Savimbi from Angola. I am 29 years old and I have got two younger sisters of same blood. Our mother died almost a year ago. We are all fighting for political asylum in South Africa. We cannot find a home in Angola anymore because of the war that our late father fought with the government of Angola until he died in that war. The government of Angola is now mad at us because our late father also wanted to be president and caused the people to fight the war for him because he was the president of UNITA political movement of Angola. So now we are in South Africa and we are suffering too much because we don't have money and the government of South Africa will not give jobs to asylum seekers. I am much concerned about my younger sisters who are finding it very difficult to manage in the situation. But I know that we should not suffer this way. I know that I must not let my younger sisters get into trouble because of money. So after consideration I am hereby begging for your assistance to help me to recover the sum of USD $29 Million which is my inheritance from my late mother. My late mother had taken this money with her to Spain in a diplomatic metal box marked (Precious Stones). Subsequently she lodged the metal box (As precious Stones) with a Securities and Valuables Protection company in Spain. I am supposed to be the beneficiary in the event of her death. However, all effort I made to go Spain to claim was refused by the Spainish embassy. And this was while it was still possible for me to travel. Now I cannot travel anywhere anymore. So in the situation that we are facing now, I must find somebody who can go to the Spain on my behalf. I understand that I will have to transfer my beneficiary rights unto you. I am willing to do so in the hope that you are a God fearing person who will not abandon us after you have the money. So from the bottom of my heart I am giving you 20% of the all the money. Once we have enough to sustain us sufficiently, you may be come our fund manager and invest the rest wisely for us. If you will be kind to assist us, please inform me urgently. Kind regards to you and your family. Sincerely, David Jonas savimbi

1 0

RE: Non-determinism, backtracking and Monads
by Simon Peyton-Jones 12 Jun '03

12 Jun '03

Check out "Embedding Prolog in Haskell", which explores exactly the topic you discuss. http://citeseer.nj.nec.com/272378.html Simon | -----Original Message----- | From: haskell-cafe-admin(a)haskell.org [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Graham | Klyne | Sent: 11 June 2003 08:38 | To: Jerzy Karczmarczuk; Haskell Cafe | Subject: Non-determinism, backtracking and Monads | | At 11:06 05/06/03 +0200, Jerzy Karczmarczuk wrote: | >I permit myself to observe that your powerset problem (and the restricted | >length problem, i.e. the combinations) is usually solved in Prolog, through | >backtracking, using reasoning/style which adopts this "individualistic" | >philosophy. | > | >powerset(<source>,<possible result>) --- is the pattern. And the | >solution is | > | >powerset([],[]). Since nothing else can be done. Otherwise you pick the item | > or not. | > | >powerset([X|Rest],L) :- powerset(Rest,L). | >powerset([X|Rest],[X|L) :- powerset(Rest,L). | > | >The xxx ++ map (x :) xxx solution in Haskell is a particular formulation | >(and optimization) of the straightforward transformation from a version | >using the non-deterministic Monad. This one is really almost a carbon copy | >of the Prolog solution, with appropriate "lifting" of operations from | >individuals to lazy lists. | | I was thinking some more about this comment of yours, and my own experience | with the ease of using lists to implement prolog-style generators, and | think I come to some better understanding. If I'm right, I assume the | following is common knowledge to experienced Haskell programmers. So, in | the spirit of testing my understanding... | | The common thread here is a non-deterministic calculation in which there | are several possible solutions for some problem. The goal is to find (a) | if there are any solutions, and (b) one, more or all of the solutions. | | Prolog does this, absent ! (cut), by backtracking through the possible | solutions. | | My first epiphany is that the Haskell idea of using a lazily evaluated list | for result of a non-deterministic computation is pretty much the same thing | (which is pretty much what you said? Is this what you mean by "the | non-deterministic monad"?). The mechanisms for accessing a list mean that | the solutions must be accessed in the order they are generated, just like | Prolog backtracking. | | So there seems to be a very close relationship between the lazy list and | non-deterministic computations, but what about other data structures? I | speculate that other structures, lazily evaluated, may also be used to | represent the results of non-deterministic computations, yet allow the | results to be accessed in a different order. And these, too, may be | (should be?) monads. If so, the Haskell approach might be viewed as a | generalization of Prolog's essentially sequential backtracking. | | In a private message concerning the powerset thread on this list, a | correspondent offered a program to evaluate the subsets in size order, | which I found particularly elegant: | | >ranked_powerset :: [a] -> [[[a]]] | >ranked_powerset = takeWhile (not . null) . foldr next_powerset ([[]] : | repeat []) | > | >next_powerset :: a -> [[[a]]] -> [[[a]]] | >next_powerset x r = zipWith (++) ([] : map (map (x:)) r) r | > | >powerset :: [a] -> [[a]] | >powerset = tail . concat . ranked_powerset | | They also pointed out that "ranked_powerset is handy since you can use it | to define combinatorial choice etc.": | | > choose :: Int -> [a] -> [[a]] | > choose k = (!! k) . ranked_powerset | | So here is an example of a different structure (a list of lists) also used | to represent a non-deterministic computation, and furthermore providing | means to access the results in some order other than a single linear | sequences (e.g. could be used to enumerate all the powersets containing the | nth member of the base set, *or* all the powersets of a given size, without | evaluating all of the other powersets). | | To test this idea, I think it should be possible to define a monad based on | a simple tree structure, which also can be used to represent the results of | a non-deterministic computation. An example of this is below, at the end | of this message, which seems to exhibit the expected properties. | | So if the idea of representing a non-deterministic computation can be | generalized from a list to a tree, why not to other data structures? My | tree monad is defined wholly in terms of reduce and fmap. Without going | through the exercise, I think the reduce function might be definable in | terms of fmap for any data type of the form "Type (Maybe a)", hence | applicable to a range of functors? In particular, I'm wondering if it can | be applied to any gmap-able structure over a Maybe type. | | I'm not sure if this is of any practical use; rather it's part of my | attempts to understand the relationship between functors and monads and | other things functional. | | #g | -- | | | [[ | -- spike-treemonad.hs | | data Tree a = L (Maybe a) | T { l,r :: Tree a } | deriving Eq | | instance (Show a) => Show (Tree a) where | show t = (showTree "" t) ++ "\n" | | showTree :: (Show a) => String -> Tree a -> String | showTree _ (L Nothing ) = "()" | showTree _ (L (Just a)) = show a | showTree i (T l r) = "( " ++ (showTree i' l) ++ "\n" ++ | i' ++ (showTree i' r) ++ " )" | where i' = ' ':' ':i | | instance Functor Tree where | fmap f (L Nothing) = L Nothing | fmap f (L (Just a)) = L (Just (f a)) | fmap f (T l r) = T (fmap f l) (fmap f r) | | reduce :: Tree (Tree a) -> Tree a | reduce (L Nothing) = L Nothing | reduce (L (Just (L Nothing ) )) = L Nothing | reduce (L (Just (L (Just a)) )) = L (Just a) | reduce (L (Just (T l r ) )) = T l r | reduce (T l r) = T (reduce l) (reduce r) | | instance Monad Tree where | -- L Nothing >>= k = L Nothing | t >>= k = reduce $ fmap k t | return x = L (Just x) | fail s = L Nothing | | -- tests | | t1 :: Tree String | t1 = T (L $ Just "1") | (T (T (T (L $ Just "211") | (L $ Just "311")) | (L Nothing)) | (L $ Just "22")) | | k1 :: a -> Tree a | k1 n = T (L $ Just n) (L $ Just n) | | r1 = t1 >>= k1 | | k2 :: String -> Tree String | k2 s@('1':_) = L $ Just s | k2 s@('2':_) = T (L $ Just s) (L $ Just s) | k2 _ = L Nothing | | r2 = t1 >>= k2 | | t3 = L Nothing :: Tree String | r3 = t3 >>= k1 | | r4 = t1 >>= k1 >>= k2 | r5 = (return "11") :: Tree String | r6 = r5 >>= k1 | | -- Check out monad laws | -- return a >>= k = k a | m1a = (return t1) >>= k1 | m1b = k1 t1 | m1c = m1a == m1b | | -- m >>= return = m | m2a = t1 >>= return | m2b = t1 | m2c = m2a == m2b | | -- m >>= (\x -> k x >>= h) = (m >>= k) >>= h | m3a = t1 >>= (\x -> k1 x >>= k2) | m3b = (t1 >>= k1) >>= k2 | m3c = m3a == m3b | ]] | | | ------------------- | Graham Klyne | <GK(a)NineByNine.org> | PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Re: Non-determinism, backtracking and Monads
by Iavor Diatchki 11 Jun '03

11 Jun '03

hello, you might also want to take a look at the "new monad library" i am working on. it is based on the old one, but does some things slightly different. one of the differences is the "nondeterminism transformer" whose implementation is inbetween lists and continuations. it also resembles resumptions quite a bit. i came up with this particular implementation but i would not be surprised if people already know about it. it is also quite simillar to the "term implementation" of the backtracking transformer described by ralf heinze in his "deriving monad transformers" paper. i would also be interested in general comments on the library. it is in the haskell cvs repository in fptools/libraries/monads (you need to check out fpconfig frist). bye iavor

1 0

Fudgets
by Christian Buschmann 11 Jun '03

11 Jun '03

Hi! Is there any easy way to display an IO String with Fudgets? I know how to display a String: import Fudgets main :: IO () main = fudlogue (shellF "Prog" showMe) showMe = ("Hello " `labLeftOfF` displayF) >==< mapF getString >==< (buttonF "ClickMe!") getString :: Click -> String getString Click = "World!" But if I change the getString-function to: getString :: Click -> IO String getString Click = return "World!" --or any other kind of function which returns an IO String I get an error message. Is there any way, without using unsafePerformIO, to display my IO String? thanks Christian Buschmann

3 3

Powerset
by oleg＠pobox.com 11 Jun '03

11 Jun '03

The following seems to be a faster version of powerset that delivers results strictly in the order of increasing cardinality (i.e., all sets of size 1 first, then of size 2, etc). It seems to run faster than any other ordered version of powerset posted so far. On GHCi, length $ powerset [1..22] is computed roughly 4 times faster than powerset3 given earlier. On Hugs, the powerset below also runs faster, with less memory consumption and in fewer GC cycles, up to a limit of 18 for the size of the input set. Then something happens. length $ powerset3 [1..19] runs out of memory on my (not current) version of Hugs too. The algorithm is more complex, though. Suppose we have a list xs Let powerset_n xs = filter (\p -> length p == n) $ powerset xs Let ps n i = powerset_n $ (tails xs)!!i that is, ps n 0 = powerset_n xs ps n (length(xs)-n) = [(tails xs)!!(length(xs)-n)] that is, i varies from 0 to (length(xs)-n) We observe that ps n (i-1) = ps n i ++ (map (x:) $ ps (n-1) i) where x = xs!!(i-1) Therefore, if we know ps (n-1) i for all i, we can compute ps n i from the base condition ps n (length(xs)-n) = [(tails xs)!!(length(xs)-n)] and then decrementing i. This recurrence is the instance of the right fold psn n psn1 = foldr (\ (psn1i,x) ps@(psni:_) -> (psni ++ (map(x:) psn1i)):ps) [[(tails xs)!!(length(xs)-n)]] $ zip (tail$init psn1) xs We can build ps n from n=0 onwards, given that ps 0 = map (const [[]]) (tails xs) we then observe that (tails xs)!!(length(xs)-n) === (reverse $ tails xs) !! n which, after a few simplifications, gives us import List powerset [] = [[]] powerset [x] = [[],[x]] powerset xs = [] : runit (tail rsxtails) ps0 where xstails = tails xs rsxtails = reverse xstails ps0 = map (const [[]]) $ tail xstails psn tn psn1 = foldr (\ xpsn1i ps@(psni:_) -> (xpsn1i++psni):ps) [[tn]] $ zipWith (\x psn1i -> map (x:) psn1i) xs (init $ psn1) runit [tn] _ = [xs] runit (tn:tns) psn1 = newps0 ++ (runit tns newps) where (newps0:newps) = psn tn psn1 There is still some room for improvement left. Actually, the following is a slightly faster version, showing off lazy evaluation: powerset [] = [[]] powerset [x] = [[],[x]] powerset xs = [] : runit (tail rsxtails) ps0 where xstails = tails xs rsxtails = reverse xstails ps0 = map (const [[]]) xstails psn tn psn1 = psnew where psnew = [tn]: (zipWith (++) (reverse (zipWith (\x psn1i -> map (x:) psn1i) xs (tail $ reverse$tail $ psn1))) psnew) runit [tn] _ = [xs] runit (tn:tns) psn1 = (last newps) ++ (runit tns newps) where newps = psn tn psn1

3 2

RE: Powerset
by Simon Marlow 10 Jun '03

10 Jun '03

> The following seems to be a faster version of powerset that delivers > results strictly in the order of increasing cardinality (i.e., all > sets of size 1 first, then of size 2, etc). It seems to run faster > than any other ordered version of powerset posted so far. On GHCi, > length $ powerset [1..22] is computed roughly 4 times faster than > powerset3 given earlier. On Hugs, the powerset below also runs faster, > with less memory consumption and in fewer GC cycles, up to a limit of > 18 for the size of the input set. Just a word of warning: using GHCi or Hugs for comparison benchmarking will give unreliable results. Use GHC with -O. Cheers, Simon

1 0

RE: Compiling hws with ghc 6
by Simon Marlow 10 Jun '03

10 Jun '03

> I'm trying to compile the haskell web server (from the > haskell-libs project > at sf.net) with ghc6 and I'm stuck on the last function in Util.hs: > > statMaybe filename = do > maybe_stat <- tryJust ioErrors (getFileStatus filename) > case maybe_stat of > Left e -> do > errno <- getErrorCode > if errno == eNOENT > then return Nothing > else ioError e > Right stat -> > return (Just stat) > > > What are the equivalents for getFileStatus and getErrorCode > these days? > > I suppose Foreign.C.Error.getErrno might substitute for > getErrorCode, but I'm stumped on getFileStatus. You're right about getErrno. getFileStatus is available from System.Posix. Cheers, Simon

1 0