- Haskell-Cafe - Haskell.org

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 11 Jun '03

11 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 10 Jun '03

10 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 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. 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

Bom dia haskell-cafe
by kandrak 10 Jun '03

10 Jun '03

Message to haskell-cafe(a)haskell.org Ola!!!! haskell-cafe GANHAMOS O PRÊMIO DE MELHOR SITE DO RAMO ======Estamos operando em Novo Formato====== Confira em: escuta21.kit.net ou http://www.escuta21.kit.net ei.... haskell-cafe Cuidado com o que fala ao Celular... ele tb tem ouvidos... para remover o haskell-cafe(a)haskell.org de nossa lista responda este e-mail e coloque remover nos perdoe o transtorno...ok? kandrak

1 0

Re: on termination
by cwitty＠newtonlabs.com 09 Jun '03

09 Jun '03

"Cagdas Ozgenc" <co19(a)cornell.edu> writes: > This may be a little off topic, but I could not get much response from = > comp.theory, so here it goes: > > Is it possible to have a programming language that can be used to = > produce only the programs that terminate, but at the same time decide = > all recursive languages? Or does such limitation automatically reduce = > the class of languages that such a programming language decide to = > primitive-recursive? If you have any programming language (say Haskell), and if you have some formal system which is capable of proving termination properties of programs in your programming language (and in which proofs are machine-checkable), then you can create a new language "Terminating Haskell" simply by pairing each program with a proof of termination. Of course, if you start with a Turing-complete language, then your formal system is necessarily incomplete; this means there will be programs that do terminate but that you cannot prove terminate. So your programming language will include programs that decide all languages that you can prove recursive (in your formal system), but not all recursive languages. However, if your formal system is strong enough, it may be possible to prove termination of all the programs you really care about. Some theorem-proving systems (including ACL2 and PVS) are like this -- within the logic, you can write programs in a Turing-complete language, as long as you can prove termination. (More precisely, the language would be Turing-complete were it not for the termination requirement. In both cases, the "program" portion is fairly distinct from the "proof of termination" portion, so that it does make sense to talk about what the language would be like without the termination requirement.) It has long been a goal of mine to create a Haskell-like programming language where you could mark portions as being guaranteed to terminate. The compiler would prove termination whenever it could, but in cases where the termination proof was too complicated for automatic proofs, the programmer would be required to add an explicit proof of termination. Carl Witty

1 0