- Haskell-Cafe - Haskell.org

User-Defined Types
by Matthias 01 May '02

01 May '02

Hello, I am a student of computer science at the university of Aachen in Germany and presently do a course about functional programming in haskell. I just wanted to introduce myself, because it is likely to happen that my posting apear frequently in the next couple of month. So my first question is about User-Defined Types. Stating the Gentle Introduction to Haskell 98 (2.2) , i already know that: "Type Constructors and date Constructors are in seperte namespaces. [example]" But according to the chapter (2.2.1) "Recursive Types" i see the polymorphic definition of a tree is: data Tree a = Leaf a | Branch (Tree a) (Tree a) where (Tree a) is obviously the data-constructor out of "the other namespace". I guess that the () is warping Tree a from the "data-constructor-namespace" into the "type-constructor-namespace". Since the gentle-intro implicitly uses (), which i am not used to - i would be happy about some hints about (). That might not be to difficult, i hope. Also i would not regret some hints about "->" which is used in function-type-definitions. I would prefer writing plus :: a,a -> a instead of the ->-variant in order to stress the distinction between arguments and returned type. What is meant that -> is "associating to the right"? Is there a name for '->'? Sincerely Matthias Pfeifer

3 3

Re: Read File
by Jorge Adriano 01 May '02

01 May '02

----------------- [moving to haskell-cafe] > I want to read some data from a text file. I accomplished it but I want to > read data from file as a Integer list for example text file has [1,2,3,5] ----------------- Wait you actually have "[1,2,3,5]" --------------------- > and when I read this data from file I handeled it as string. What can I do > to get it as integer list. Hint: map read ["1","2","3"] ::[Int] ------------------- this would be helpfull if you had "1 2 3 5". It's easier then Hint: read "[1,2,3,5]"::[Int] J.A.

1 0

Re: Read File
by Jorge Adriano 01 May '02

01 May '02

[moving to haskell-cafe] > I want to read some data from a text file. I accomplished it but I want to > read data from file as a Integer list for example text file has [1,2,3,5] > and when I read this data from file I handeled it as string. What can I do > to get it as integer list. Hint: map read ["1","2","3"] ::[Int] J.A.

1 0

(no subject)
by Ricky Kurniawan 30 Apr '02

30 Apr '02

1 0

some algorithms are hard to code in O(n) in Haskell
by klusacek＠atrey.karlin.mff.cuni.cz 29 Apr '02

29 Apr '02

Hi - does anybody know how to do a term unification in Haskell in O(n), where n is length of the input terms? I know Montanari-Martelli algorithm for this, but I'm unable to code it in Haskell (in O(n)). I would need a destructive update of the directed graph representing terms (to do a substitution) and checking for cycles in directed graphs (these cycles emerge when unifying things like x=f(x) -- their detection is also called occurs-check). I've been trying hard but still have no solution. Maybe I'm not smart enough, maybe I don't know some trick, maybe it's impossible in Haskell. Thanks, _dave_

2 1

Re: Binary search tree
by Rijk J. C. van Haaften 29 Apr '02

29 Apr '02

>Hi everybody, > >I studied haskell this semester at the university and I was required to >implement a binary search tree in haskell. >I would appreciate if anyone could send me an example code of this data >structure. Just read a standard textbook. Some useful course notes by Jeroen Fokker are available online at http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Enough to solve your problem. Rijk-Jan van Haaften

1 0

Binary search tree
by Claudio Marcio de Souza Vicente 29 Apr '02

29 Apr '02

Hi everybody, I studied haskell this semester at the university and I was required to implement a binary search tree in haskell. I would appreciate if anyone could send me an example code of this data structure. thanks in advance, Claudio

1 0

RE: defining (-> Bool) as a set
by Hal Daume III 26 Apr '02

26 Apr '02

Would there be any problems if there were an artificial "<-" type constructor in Haskell which was basically: type a <- b = b -> a but not a type synonym so you could define it to be instances of classes, but then those get applied "backwards" to ->? Okay, that made no sense. I'll try again. Type lambda = bad (undecidable). What about only type lambda on function types and not even type lambda; simply allow partial application to the second argument *only* on ->? This would solve my problem and I believe that of an earlier poster who wanted to define catamorphisms (I think; don't feel like checking), but couldn't because of this restriction. Is this still "too loose" to be made to work? -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Mon, 22 Apr 2002, Simon Peyton-Jones wrote: > Hal, > > [I think this sort of question would be better on the haskell-cafe > list.] > > I don't think what you want can be done directly. It's the old > thing about not having lambdas at the type level. You want: > > instance Eq a => Coll (\x. x -> Bool) a where ... > > and you just can't do that. You *can* abstract the second argument > of (->): > > instance Eq a => Coll ((->) Bool) a where ... > > but not the first. It's a well known shortcoming in Haskell, that you > can > partially apply type constructors, but you can't do argument > permutation. > > I know of no good solution. Adding type lambdas in their full glory > makes type inference pretty much impossible. What we'd like is > a compromise. Maybe someone can invent one. But take care. > The ground is littered with corpses. > > Simon > > > | -----Original Message----- > | From: Hal Daume III [mailto:hdaume@ISI.EDU] > | Sent: 23 April 2002 01:30 > | To: Jorge Adriano > | Cc: Haskell Mailing List > | Subject: Re: defining (-> Bool) as a set > | > | > | Yeah, both options suggested are valid, of course. But I > | really don't want to have a constructor and I'm using Edison > | where Coll is defined something like: > | > | class Coll c e where > | empty :: c e > | insert :: c e -> e -> c e > | > | etc., which precludes the fun dep solution. > | > | - Hal > | > | -- > | Hal Daume III > | > | "Computer science is no more about computers | hdaume(a)isi.edu > | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume > | > | On Tue, 23 Apr 2002, Jorge Adriano wrote: > | > | > > | > > class Collection e ce | ce -> e where > | > > empty :: ce > | > > insert :: e -> ce -> ce > | > > member :: e -> ce -> Bool > | > > > | > > instance Eq a => Collection a (a -> Bool) where > | > > empty = (\x -> False) > | > > insert e f = (\x -> if x == e then True else f x) > | > > member e f = f e > | > > | > This is way better than my solution... > | > > | > I had never used multi-parameter classes before, so I forgot the > | > functional > | > dependency (right name? the "|ce->e"), and there was > | obviously no need for my > | > extra constructor. > | > > | > J.A. > | > > | > | _______________________________________________ > | Haskell mailing list > | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell > | >

1 0

RE: lazy comparison for equality ?
by Konst Sushenko 24 Apr '02

24 Apr '02

In addition to what Hal said, I think that even assuming that you want to write a function like that that is only supposed to be applied to finite lists (like, say, prelude's 'and' function, which does not terminate on an infinite list of True values) you still cannot do it because haskell lists are not like C lists. There is no notion, to my understanding, of list circularity. There are finite and infinite lists. Your example of a list that you call a circular list is just a definition of a recursive function that produces an infinite list. So what you are almost asking is how to write a function that checks if a list has repeated sub-sequences, which is not of course precisely the same that you asked (because even a finite list can have repeated sub-sequences), but close. And this is just one of many problems taken care of by various string search algorithms. konst > -----Original Message----- > From: Hal Daume III [mailto:hdaume@ISI.EDU] > Sent: Wednesday, April 24, 2002 12:38 PM > To: klusacek(a)atrey.karlin.mff.cuni.cz > Cc: haskell-cafe(a)haskell.org > Subject: Re: lazy comparison for equality ? > > > I don't think you can write such a function. For instance, > how would you > know whether [1..] is circular or not? In order to know that it's not > you'd need to evaluate it fully. > > -- > Hal Daume III > > "Computer science is no more about computers | hdaume(a)isi.edu > than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume > > On Wed, 24 Apr 2002 klusacek(a)atrey.karlin.mff.cuni.cz wrote: > > > > > Hi - > > I'm a Haskell beginner and I have a problem. > > > > Let's have a list which may be normal list > > list1 = [1,2,3] > > or a circular list > > list2 = 1:2:list2 > > > > Now I'd like to have a function which tells me whether the > > given list is circular or not. This doesn't work: > > > > circ l = l l > > circ2 l [] = False > > circ2 l (_:as) | l==as = True > > | True = (circ2 l as) > > > > > > It seems that comparison l==as really compares element by > element thus > > falling into an infinite loop. I would need to compare > pointers instead of > > values. > > > > Does anybody know how this could be done ? > > > > Thanks. > > > > > > > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

lazy comparison for equality ?
by klusacek＠atrey.karlin.mff.cuni.cz 24 Apr '02

24 Apr '02

Hi - I'm a Haskell beginner and I have a problem. Let's have a list which may be normal list list1 = [1,2,3] or a circular list list2 = 1:2:list2 Now I'd like to have a function which tells me whether the given list is circular or not. This doesn't work: circ l = l l circ2 l [] = False circ2 l (_:as) | l==as = True | True = (circ2 l as) It seems that comparison l==as really compares element by element thus falling into an infinite loop. I would need to compare pointers instead of values. Does anybody know how this could be done ? Thanks.

2 1