Re: [Haskell-cafe] Proposal: Non-recursive let
I support Oleg's proposal. A shadowing, non-recursive let would be a useful tool. As starter suggestions for the keyword or syntax, I submit: let new x = expr in body -- Not the old x! let shadowing x = expr in body shadow x = expr in body let x =! expr in body -- The explosive bang gives an imperative flavor. Other suggestions would be welcome. Ezra On Wed, Jul 10, 2013, at 01:47 AM, o...@okmij.org wrote: > > I have also had problems with non-termination, unintended recursion. > The problem is not caught statically and leads to looping, which may > be quite difficult to debug. Andreas should tell his story. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] for = flip map
I would very much like to see a standard function for "flip map" along these lines. I think it would make a lot of code more readable. Like the OP, I use "for" in my own code. It's unfortunate that Data.Traversable takes the name with another type. Two options would be to (a) reuse the name in Data.List and force people to qualify as necessary, or (b) choose another name for "flip map". Regarding other possible names: forall is a keyword and forAll is used by QuickCheck. One possibility would be "foreach". Ezra On Wed, Mar 28, 2012, at 10:19 PM, Christopher Done wrote: > On 28 March 2012 22:05, Matthew Steele wrote: > > Doesn't for already exist, in Data.Traversable? Except that for = > > flip traverse. > > Traverse doesn't fit the type of fmap, it demands an extra type > constructor: > > traverse :: (Traversable t,Applicative f) => (a -> f b) -> t a -> f (t b) > > fmap :: Functor f => (a -> b) -> f a -> f b > > Note the (a -> f b) instead of (a -> b). > > E.g. > > fmap :: (a -> b) -> [a] -> [b] > > can't be expressed with traverse, you can only get this far: > > traverse :: (a -> [b]) -> [a] -> [[b]] > > Unless I'm missing something. > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Quick check finite data generation
Mukesh, You need to write a generator function for the type (IntMap Index) which keeps track of the n parameter that you're using in arbIndex. You can't rely on the Arbitrary instance for (IntMap a) because it doesn't have access to the n parameter that you are so controlling in arbIndex. (Actually, you could use the "size" number that QuickCheck keeps behind the scenes, using the functions "sized" and "resize", but that would have the consequence of affecting all other arbitrary values generated as part of that recursion--including the floats and ints and so on, which may or may not be what you want.) Also, since your trees are unranked, rather than binary as in the paper example, take care with the factor of 2 that you're using to resize the generated subtrees. You might find that the resulting trees are still much bigger than you want, or have different statistical properties. Hope that helps-- Ezra On Friday, September 23, 2011 4:22 AM, "mukesh tiwari" wrote: Hello all I have a data type data Index = Index {indexSize::Float, indexIds::[Int], indexDown::(IntMap.IntMap Index)} | IndexLeaf {indexSize::Float, indexIds::[Int]} | IndexEmpty {indexSize::Float} deriving ( Show , Eq ) I derived some thing like this for QuickCheck testing instance Arbitrary a => Arbitrary ( IntMap a ) where arbitrary = liftM IntMap.fromList arbitrary instance Arbitrary Index where arbitrary = oneof [ liftM3 Index arbitrary arbitrary arbitrary , liftM2 IndexLeaf arbitrary arbitrary , liftM IndexEmpty arbitrary ] but its generating infinite list of data. After reading the paper [1]QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs i tried to write above one using sized but i am not sure how to write this . instance Arbitrary a => Arbitrary ( IntMap a ) where arbitrary = liftM IntMap.fromList arbitrary instance Arbitrary Index where arbitrary = sized arbIndex arbIndex 0 = liftM IndexEmpty arbitrary arbIndex 1 = liftM2 IndexLeaf arbitrary arbitrary arbIndex n = frequency [ ( 1 , liftM IndexEmpty arbitrary ) , ( 1 , liftM2 IndexLeaf arbitrary arbitrary ) , ( 2 , liftM2 Index arbitrary arbitrary ( arbIndex $ div n 2 ) ) ] but from this type i can see arbIndex $ div n 2 will return Gen Index not Gen ( IntMap Index ) and i am getting compiler error . Could some one please tell me , how to write arbIndex n in terms of smaller n like in the paper arbTree 0 = liftM Leaf arbitrary arbTree n = frequency[ ( 1 , liftM Leaf arbitrary ) , ( 4 , liftM2 Branch ( arbTree $ div n 2 ) ( arbTree $ div n 2 ) ) ] Thank You Mukesh Tiwari ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe References Visible links 1. http://www.eecs.northwestern.edu/%7Erobby/courses/395-495-2009-fall/quick.pdf Hidden links: 2. http://www.eecs.northwestern.edu/%7Erobby/courses/395-495-2009-fall/quick.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why the name lambda calculus?
An algebra is a specific kind of structure which is itself formalized mathematically. I've never seen a formalization of the notion of "a calculus" and I believe it to be a looser term, as KC defined it. Specifically, an algebra consists of a set (or several "sorts" of sets) and operations that reduce pairs of elements from that set (or the pairs can be triples, etc.) back into the set. Usually that set corresponds to the "semantics" of the algebra, and syntactic equations like xy = yx exist in a different realm from the operations and their actions. Lambda calculus differs from an algebra by having a construct (lambda abstraction) that only makes sense if you know the syntactic structure of the term it applies to. That is, it has a binding construct. You could define lambda calculus as an algebra by taking the underlying set to be the syntax of the calculus itself, but that would require infinitely many operations (a lambda-binder for each variable) and equations, so perhaps that would be awkward. Pi calculus, like lambda calculus, has binders, while "process algebras" are usually defined via operations on processes. I believe this to be a general trait of things described as "calculi"--that they have some form of name-binders, but I have never seen that observation written down. I'm sure that an algebraist could give a more definite answer about this. Ezra On Aug 23, 2011, at 12:19 PM, Rajesh S R wrote: > Slight digression. Why not Lambda "Algebra"? > In particular, what is the criteria for a system to be calculus and how's it > different from algebra? > > On Mon, Aug 22, 2011 at 12:41 AM, Jack Henahan wrote: > The short answer is "because Church said so". But yes, it is basically > because λ is the abstraction operator in the calculus. > > Why not alpha or beta calculus? What would we call alpha and beta conversion, > then? :D > > On Aug 21, 2011, at 12:37 PM, C K Kashyap wrote: > > > Hi, > > Can someone please tell me what is the root of the name lambda calculus? Is > > it just because of the symbol lambda that is used? > > Why not alpha or beta calculus? > > Regards, > > Kashyap > > ___ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > Jack Henahan > jhena...@uvm.edu > == > Computer science is no more about computers than astronomy is about > telescopes. > -- Edsger Dijkstra > == > > > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > -- > Rajesh S R > http://rajeshsr.co.cc/blogs/ > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tracer for Haskell showing substitutions
Hi, "Hat": The Haskell Tracer. http://www.haskell.org/hat/ >From the site: Hat helps locating errors in programs. Furthermore, it is useful for understanding how a (correct) program works, especially for teaching and program maintenance. Hat is not a time or space profiler. Hat can be used for programs that terminate normally, that terminate with an error message or that terminate when interrupted by the programmer. "Vital"/"Pivotal": it's dead, but it may be interesting to you anyway. http://www.cs.kent.ac.uk/projects/pivotal/ http://www.cs.kent.ac.uk/projects/vital/ >From the site: Pivotal has similar goals to its predecessor system, Vital. In particular: * Documents are live in the sense that, if a document is changed, the displayed values are automatically re-evaluated. Thus documents are always in a consistent state. * Direct manipulation of ADT values is supported. That is, an end user is able to manipulate the text of a Haskell module simply by point-and-click mouse operations on displayed values. Pen and paper work too. Ezra. Ulrik Rasmussen-2 wrote: > > Hi all, > > I was wondering if someone has written a tracer/debugger that shows you > how a given Haskell expression is evaluated, by generating all the > intermediate states of the expression until it is in normal form? > > For instance, given the following code: > >> take' 0 xs = [] >> take' n (x:xs) = x : take' (n-1) xs >> exp = take' 2 [1,2,3,4,5,6] > > the trace of 'exp' would generate something like this: > >> exp = take' 2 [1,2,3,4,5,6] >> exp = (\n (x:xs) -> x : take' (n-1) xs) 2 [1,2,3,4,5,6] >> exp = 1 : take' (2-1) [2,3,4,5,6] >> exp = 1 : take' 1 [2,3,4,5,6] >> exp = 1 : (\n (x:xs) -> x : take' (n-1) xs) 1 [2,3,4,5,6] >> exp = 1 : 2 : take' (1-1) [3,4,5,6] >> exp = 1 : 2 : take' 0 [3,4,5,6] >> exp = 1 : 2 : (\0 xs -> []) 0 [3,4,5,6] >> exp = 1 : 2 : [] >> exp = [1,2] > > That is, all the substitutions performed when evaluating 'exp' from left > to right. > > I was thinking that something like this could be rather useful when > teaching or learning Haskell. > > > Thanks, > > Ulrik > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://old.nabble.com/Tracer-for-Haskell-showing-substitutions-tp27421880p27424789.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] cursive to foldr
Using the same basic structure you did, and foldr, I think below is the simplest method: import Data.Maybe searchList :: (a -> Bool) -> [a] -> Maybe [a] searchList p xs = foldr (\x acc -> if p x then Just (x: fromMaybe [] acc) else acc) Nothing xs ghci> searchList (=='o') "A quick brown fox" Just "oo" ghci> searchList (==' ') "A quick brown fox" Just " " ghci> searchList (=='z') "A quick brown fox" Nothing >From maybe gets rid of the Maybe, so that our recursive call works: ghci> fromMaybe [] (Just [1..3]) [1,2,3] That's why we got the error below when we tried without fromMaybe; on subsequent applications of foldr, the type would have to change. :1:51: Couldn't match expected type `[a]' against inferred type `Maybe [a]' In the expression: if p x then Just (x : acc) else acc In the first argument of `foldr', namely `(\ x acc -> if p x then Just (x : acc) else acc)' In the expression: foldr (\ x acc -> if p x then Just (x : acc) else acc) Nothing xs I have a feeling that using fromMaybe is not the best way, but it gets the job done for now. On that note; if somebody with some more experience would chime in, that'd be awesome. ;) Ezra dima.neg wrote: > > How can I do this using foldr? > > searchList p [] = Nothing > searchList p (x:xs) > | p x = Just (x:filter p xs) > | otherwise = searchList p xs > > > I try this: > searchList p xs = foldr (\x acc -> if p x then Just (x:acc) else acc) > Nothing xs > but don't work. > > Thanks > -- View this message in context: http://old.nabble.com/Recursive-to-foldr-tp26368900p26399795.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help to solve simple problem !
The following program should work: ===compress.hs= toList :: (Eq a) => [a] -> [[a]] toList [] = [] toList x = start : toList end where (start, end) = span (==(head x)) x toTuple :: [a] -> (a, Int) toTuple x = (head x, length x) compress :: Eq a => [a] -> [(a, Int)] compress x = map toTuple $ toList x = The important thing to understand here, is the "span" function from the Prelude, and apply it recursively. *Main> span (=='A') "AAABCC" ("AAA","BCC") *Main> span (=='h') "hhhaskell" ("hhh","askell") I've used a function "toList" to separate each part of the string into a separate element of a list: *Main> toList "AAABCC" ["AAA","B","CC"] *Main> toList "EEEZZZRR!!" ["EEE","ZZZ","RR","","!!"] >From there, "toTuple" takes the first letter of the string, and puts it with its length in a tuple: *Main> toTuple "EEE" ('E',3) *Main> toTuple "E" ('E',5) Because of how it's defined, we also get the following: *Main> toTuple "Ezra" ('E',4) But that won't matter if we only use it after "toList", as in "compress". Also, I've used your type signature for my solution, not your example output; if you want it to be displayed like that, you'll have to write your own function for printing. This solution is probably not optimal, but it's a start. Hope that helps, Ezra Aneto wrote: > > Hi ! I am beginner in Haskell and have problems with this problem: > compress :: Eq a => [a] -> [(a, Int)] > If you have string "AAABCCC" it transforms it to : {A, 3} {B,1} {C,3} > > Could you help me with it ? > Thank you in advance ! > -- View this message in context: http://old.nabble.com/Help-to-solve-simple-problem-%21-tp26249028p26292205.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to print a string (lazily)
On Jan 3, 2006, at 6:30 PM, Sebastian Sylvan wrote: On 1/3/06, Daniel Carrera <[EMAIL PROTECTED]> wrote: Neil Mitchell wrote: All Haskell functions are lazy, hence there is no need to "write a lazy version" of your print_list function. I think the function you probably want is: putStr (unlines xs) Hhmm... that does work, and I'm a bit surprised that it does. I guess I'm still stuck in the eager computation mindset. I would expect putStr to have to wait for the (unlines xs) to be finished before doing any printing, but it doesn't. Some day I'll get the hang of this lazy evaluation thing. :) It does, in a sense, but since unlines is lazy (just like *everything else* in Haskell) it won't actually *do* anything until putStr demands an element from the result. ... and, significantly, putStr will demand those elements one at a time; each element of the list is, in turn, evaluated lazily, producing (a) a next element and (b) a thunk representing the rest of the list. In your example 'join' function, join [] = "" join (x:xs) = (show x) ++ "\n" ++ join xs the caller will demand the first element of the list, which will force the evaluation of (show x) but it will not immediately force the evaluation of (join xs). That part stays as it is, living life as a thunk, until the caller has demanded all the preceding elements and still wants more. hth, Ezra ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Two questions: lazy evaluation and Church-Rosser
Gregory, Church-Rosser is proved in any good text on lambda calculus, such as Barendregt [1]. Some rather detailed notes on that book are at [2]. Lazy evaluation is often formalized as "call-by-need." Try [3]. Ezra [1] Barendregt. The Lambda Calculus <http://www.amazon.com/exec/obidos/ASIN/0444875085> [2] <http://www.andrew.cmu.edu/user/cebrown/notes/barendregt.html> [3] Maraist, Odersky, and Wadler, "A call-by-need lambda-calculus." Journal of Functional Programming 8(3):275-317 (May 1998). <http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html> On Nov 15, 2005, at 5:30 AM, Gregory Woodhouse wrote: This is surely a dumb question, but where can I find a proof of the Church-Rosser theorem? Now, a totally(?) separate question: I've been trying to do some background reading on lambda calculus, and have found discussions of strict evaluation strategies (call-by-value and call-by-name) but have yet to find an appropriate framework for modeling lazy evaluation (much less infinite lists and comprehensions). Can anyone point me in the right direction? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe