December 2008 - Beginners

about the concatenation on a tree
by Max cs 04 Jan '09

04 Jan '09

hi all, not sure if there is someone still working during holiday like me : ) I got a little problem in implementing some operations on tree. suppose we have a tree date type defined: data Tree a = Leaf a | Branch (Tree a) (Tree a) I want to do a concatenation on these tree just like the concat on list. Anyone has idea on it? or there are some existing implementation? Thank you and Happy New Year! regards, Max

3 3

bottom case in proof by induction
by raeck＠msn.com 31 Dec '08

31 Dec '08

Dear all, Happy New Year! I am learning the Induction Proof over Haskell, I saw some proofs for the equivalence of two functions will have a case called 'bottom' but some of them do no have. What kind of situation we should also include the bottom case to the proof? How about the functions do not have the 'bottom' input such as: foo [] = [] foo (x:xs) = x : (foo xs) thank you, Raeck

3 2

Re: about the concatenation on a tree
by Thomas Davie 31 Dec '08

31 Dec '08

On 31 Dec 2008, at 22:38, Max.cs wrote: > Hi Bob, > > Actually I am a fresher in the university and I am doing a > additional exercise for the holiday. > > I think your modification is great, but I am afraid I have to keep > the original forms of the function and data type. I am given the > following code: > >> data Tree a = Leaf a | Branch (Tree a) (Tree a) > >> foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b >> foldTree f g (Leaf x) = f x >> foldTree f g (Branch t1 t2) = g (foldTree f g t1) (foldTree f g t2) > > now, what I am asked to do is to complete the following function > concatT using the above foldTree. > >> concatT :: Tree (Tree a) -> Tree a > > the example output of concatT are also given as: > > concatT (Leaf t) = t > concatT (Branch (Leaf t1) (Leaf t2)) = Branch t1 t2 > > I am confused by the type of function concatT and foldTree: > > From the output example, we know, the output should be t (atomic > value) when the input is (Leaf t), and the output will be Branch t1 > t2 (a Branch) when the input is a Branch. But the the definition of > foldTree, the return type of f and g should be the same (both are > b). Am I missing some important point? Any idea on how we can > implement the function concatT ? Sure, but lets go through (most of) the process. We know the function we need has the type Tree (Tree c) -> Tree c. You'll see why I used c as my variable in a minute, and we're given a function with the type (a -> b) -> (b -> b -> b) -> Tree a -> b. Lets try and make that into the type we need. We know the result type must be "Tree c", so lets try replacing all bs with Tree cs: someFunction :: (a -> Tree c) -> (Tree c -> Tree c -> Tree c) -> Tree a -> Tree c We also know that the argument type we want is not a Tree of any values, but actually a Tree of Tree cs, so lets supstitute a for Tree c too: someOtherFunction :: (Tree c -> Tree c) -> (Tree c -> Tree c -> Tree c) -> Tree (Tree c) -> Tree c As we know, in Haskell functions are curried, so this type is the same as (Tree c -> Tree c) -> ((Tree c -> Tree c -> Tree c) -> (Tree (Tree c) -> Tree c)). Note that the last part here is exactly the type we need, so if we provide foldTree with the right two functions, it looks like it's gonna do exactly what we want. Lets look at the rules for foldTree – it applies f wherever it meets a Leaf, and g wherever it meets a Branch, so lets think about what we want to do in those two situations. In the case of a Leaf, we'd like to replace the leaf with it's value, so the function we're looking for sounds a lot like it does nothing much. In the case of Branches, we'd like to leave them in place, so we probably want to look at the Branch creator function. I'll leave the rest to you :) > Btw, it will be much better if you do not send this email and the > replies to the maillist for this instance, since I think it is not a > very good idea to let my tutor know I am asking question involved in > the exercise. Just let me know if you dont know you want to answer > this question : ) I'm sure your tutor doesn't mind you asking for help, in fact, he's probably the first guy you should go and ask for some help. What he will want to know is exactly how much help you're getting, and how you're doing with the subject matter – remember, he's trying to teach you, not trying to torture you :). Because of that, I have forwarded this email to the mailing list, you're welcome to use my help or not, depending on how guilty you feel (although unless this is a test, any guilt you feel is entirely in error). Bob

1 0

IO Question
by Nathan Holden 30 Dec '08

30 Dec '08

I've been playing around with some types, and such, and I can get some basic IO. But the thing that confused me is this: How is it that IO [Char] == [Char] can be True, but IO a == a is a type error? How can you implement eq for a type so that IO (type) == type?

2 1

Re: [Haskell-cafe] represent data sturcture using function
by Ryan Ingram 30 Dec '08

30 Dec '08

On Mon, Dec 29, 2008 at 4:29 AM, <raeck(a)msn.com> wrote: > Would you please give me a complete example of code that I could have more > information > on the idea? Sure, I put up an example at http://ryani.freeshell.org/haskell/gmap.hs class MapKey k where data (:->) k :: * -> * newMap :: (k -> v) -> (k :-> v) fetch :: (k :-> v) -> (k -> v) update :: k -> (v -> v) -> (k :-> v) -> (k :-> v) assign :: k -> v -> (k :-> v) -> (k :-> v) assign k v m = update k (const v) m empty :: v -> (k :-> v) empty = newMap . const with instances & associated data types: instance MapKey () where -- A single value newtype () :-> v = UMap v instance MapKey Bool where -- A value for False and True data Bool :-> v = BMap v v instance (MapKey k1, MapKey k2) => MapKey (k1,k2) where -- A "curried" map newtype (k1,k2) :-> v = PMap (k1 :-> k2 :-> v) instance (MapKey k1, MapKey k2) => MapKey (Either k1 k2) where -- sub-maps for Left k1 and Right k2 data (Either k1 k2 :-> v) = EMap (k1 :-> v) (k2 :-> v) instance MapKey k => MapKey (Maybe k) where -- Now we can build up from existing structures! newtype (Maybe k) :-> v = MaybeM (Either () k :-> v) instance MapKey k => MapKey [k] where -- Value for [] and map for (head:tail) -- -- Note that this includes a recursive ([k] :-> v) map -- in the pair map (k,[k]) :-> v data [k] :-> v = ListM v ((k,[k]) :-> v) instance MapKey Positive where -- We just convert a positive number into -- a list of Bools, then make a map of those newtype Positive :-> v = PosMap ([Bool] :-> v) instance MapKey Integer where -- Now an integer is either negative, zero, or positive. -- So we store a map for negative numbers, a zero value, -- and a map for positive numbers. data Integer :-> v = IntMap (Positive :-> v) v (Positive :-> v) The rest of the class functions are reasonably easy to derive from their type and these data types. -- ryan

6 5

represent data sturcture using function
by Raeck chiu 30 Dec '08

30 Dec '08

Merry Christmas! Hope everybody is enjoying the Christmas! I am doing some readings and I found something seems to be interesting. People sometime will try to represent a quantity-regard-only data structure (such a order-regadless List) using functions instead of ta concrete data structure (like the haskell build-in []), any particular reason for this? For example, > data Sex = Male | Female > classA :: Sex -> Int > classA Male = 100 > classA Female = 200 when I should prefer the above solution instead of using a concrete data structure such as [] to represent the classA members? It seems to be very difficult to change the number of Male or Female if a concrete data structure is not used. Is it possible change the number of Male in classA when represent classA using function? Thank you very much! Best wishes, Raeck _________________________________________________________________ It’s the same Hotmail®. If by “same” you mean up to 70% faster. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_…

6 7

Restricting integers in a type?
by Colin Paul Adams 30 Dec '08

30 Dec '08

Hello, I want to declare a type thus: type Coordinate = (Int, Int) But the two integers must be confined to the inclusive range 0-11. Can i express that in the type system? -- Colin Adams Preston Lancashire

3 7

about Data.BinaryTree
by Liu Jian 29 Dec '08

29 Dec '08

Hi All, Is there any implementation of binary tree in haskell library? for example, "insert lookup empty adjust isEmpty delete" including in it. cheers, --- email to: gjk.liu(a)gmail.com

2 1

MULTICONF-09 call for papers
by Ed 27 Dec '08

27 Dec '08

MULTICONF-09 call for papers The 2009 Multi Conference in Computer Science, Information Technology and Control systems and Computational Science and Computer Engineering (MULTICONF-09) (website: http://www.PromoteResearch.org) will be held during July 13-16 2009 in Orlando, FL, USA. We invite draft paper submissions. The event consists of the following conferences: · International Conference on Artificial Intelligence and Pattern Recognition (AIPR-09) · International Conference on Automation, Robotics and Control Systems (ARCS-09) · International Conference on Bioinformatics, Computational Biology, Genomics and Chemoinformatics (BCBGC-09) · International Conference on Enterprise Information Systems and Web Technologies (EISWT-09) · International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-09) · International Conference on Information Security and Privacy (ISP-09) · International Conference on Recent Advances in Information Technology and Applications (RAITA-09) · International Conference on Software Engineering Theory and Practice (SETP-09) · International Conference on Theory and Applications of Computational Science (TACS-09) · International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09) The website http://www.PromoteResearch.org contains more details. Sincerely John Edward Publicity committee

1 0

Defining a containing function on polymorphic list
by Raeck Zhao 24 Dec '08

24 Dec '08

I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes: > contain :: a -> [a] -> Bool > contain x [] = False > contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check? Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck _________________________________________________________________ It’s the same Hotmail®. If by “same” you mean up to 70% faster. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_…

8 12