- Haskell-Cafe - Haskell.org

type equivalency
by Cagdas Ozgenc 06 Jun '02

06 Jun '02

Greetings. I know 2 special type constructors(there might be other that I do not know yet) -> and ( , ) where structural type equivalency is enforced and we can also create new types with an algebric type constructor notation where name equivalency is enforced. What is the rationale? I mean why 2 special type constructors, but not 5, or 10 or N? Thanks for taking time.

5 8

(no subject)
by xoo 06 Jun '02

06 Jun '02

hi.. i was just wondering if some body could give a simple equation for the following situation.other than recursion plz.. occurrences :: Eq a => a -> [a] -> [a] --occurrences xs ys returns the number of times that xs occurs in ys thanks

2 1

Re: Type equivalency 2
by Ashley Yakeley 06 Jun '02

06 Jun '02

At 2002-06-06 03:38, Cagdas Ozgenc wrote: >Then either -> is not a type constructor, (->) is a type constructor. >or the concept of type >constructors has to be divided into two : consuming type constructors, and >producing type constructors. Type constructors can do anything they like with their arguments. Here are some of kind (* -> *): newtype Holds a = MkHolds a data Ignores a = MkIgnores newtype Wants a = MkWants (a -> Bool) data List a = MkPairList a (List a) | MkEmptyList data Maybe a = Just a | Nothing I don't think you can divide them up into two categories... -- Ashley Yakeley, Seattle WA

1 0

��ʦ��ǻۣ��ȡ��ҵ�ҵ��ţ�ֱ��ɹ��ʿ��Ľ��
by ��Ż�չЭ�� 06 Jun '02

06 Jun '02

1 0

Re: Type equivalency 2
by Ashley Yakeley 06 Jun '02

06 Jun '02

At 2002-06-06 00:40, Cagdas Ozgenc wrote: >From the previous discussion it has been brought to my attention that there >is no much difference between > >a -> b > >and > >data F a b = Blank a b -- "-> probably has a blank value constructor" Well F and (->) may both be type-constructors of kind (* -> * -> *), but I think there the similarity ends. You may consider an F as holding an 'a' and a 'b', but a function holds a 'b' for every 'a'. It's quite different, and F does not implement functions. If you're wondering about the value constructor for a function, ask yourself, what would you pass to it? You could do this, though: newtype F' a b = MkF' (a -> b) ...or this: type F'' = (->) I think you'll find (->) is pretty much atomic. It's tempting to say a function is constructed from a piece of code, but for a lazy language pretty much any value might be represented by a piece of code... -- Ashley Yakeley, Seattle WA

1 0

Re: type equivalency
by Jon Cast 06 Jun '02

06 Jun '02

Andrew J Bromage <andrew(a)bromage.org> wrote: > G'day all. > On Wed, Jun 05, 2002 at 08:20:03PM -0500, Jon Cast wrote: > > I think you're confused about what the type declarations mean. > > When you say > > > sqrt :: Float -> Float > > you're promising to operate over /all/ Floats. > That would be true of Haskell functions were constrained to be total > functions. They are not. Sqrt takes values of type Float, but it > just happens to be a partial function over that type. That depends on what you mean by ``partial function''. Technically, of course, a function of type (a -> b) is a subset of (a x b) satisfying certain constraints. All Haskell functions f satisfy the property (forall x::a. exists y::b. (x, y) <- f), so you can always get a value of f at any x. In other words, sqrt can take any x and compute with it; it just delivers _|_ at some of them. My point was, (sqrt x) is legal Haskell (and has a value) for all (x :: Float). > > Unfortunately, Haskell doesn't allow {x :: Float | x >= 0} as a > > type, nor does it provide a positive-only floating point type. > One general rule of strongly-typed programming is: A program is type > correct if it is accepted by my favourite type checker. A corollary > is that what you call a type, I reserve the right to call a > precondition. If I accepted that, I would be un-defining crucial terms. That would destroy the potential for discussion here, no? > Cheers, > Andrew Bromage Jon Cast

4 3

Re: type equivalency
by Jon Cast 05 Jun '02

05 Jun '02

Cagdas Ozgenc <co19(a)cornell.edu> wrote: > For example all functions with Int -> Int are type equivalent, > because structural equivalency is used. Most of the time the > functions are not compatible because they have different pre/post > conditions, even though they seem to have the same input output > types. I rather make my functions an instance of a type-class to > tell the compiler that they can be used interchangably. For example > sqrt :: Float -> Float > sqrt a = /* pre : a >= 0 */ > negate :: Float -> Float > /* no precondition */ > are different functions. You cannot just plug one in place of > another (you can in Haskell because of structural type equivalency). I think you're confused about what the type declarations mean. When you say > sqrt :: Float -> Float you're promising to operate over /all/ Floats. If you want to restrict that to only certain Floats, you would need a different ``type'': > sqrt :: {x :: Float | x >= 0} -> Float or introduce your own type isomorphic to this. Unfortunately, Haskell doesn't allow {x :: Float | x >= 0} as a type, nor does it provide a positive-only floating point type. I think your problem is related to the concepts of ``different'' and ``plug in''. All the Haskell compiler performs is type checking; unfortunately, type checking is purely structural; it doesn't enquire whether the resulting program is correct (or even meaningful). You can tell Haskell isn't concerned with whether your programs are meaningful, because Haskell allows the following program: > main = main This is obviously completely meaningless. Now, then, obviously sqrt and negate are different in the sense of ``unequal''. If you don't know, equality between Haskell functions is defined (ommitting some complications) like such: > f = g <=> forall x.f x = g x Clearly negate /= sqrt! However, taking your notion of ``not different'', which is apparantly > f = g <=> domain f = domain g note that both > sqrt x = x ** (1/2) and > qrrt x = x ** (1/4) have the same domain. Are they equivalent? It (obviously) depends on the context. Consider the function dist: > dist :: (Double, Double) -> (Double, Double) -> Double > dist (x1, x2) (y1, y2) = sqrt ((x1 - y1) ** 2 + (x2 - y2) ** 2) You can't use qrrt in dist and expect it to be correct any more than you an use negate. On the other hand there may be terms which don't care which among qrrt and sqrt you give them but don't want negate. So, equivalence is a tricky problem---and one you can't solve without reading the programmer's mind. That's why Haskell doesn't address it, being content with type checking. > Also a function working over (Int,Int) will do so even if the > numbers are totally irrelevant to that function. They maybe the > number of (apples,oranges) or number of (books,authors). You're right that the type constructor (,) doesn't carry a lot of information; but I think you misunderstand why: given a type declaration > data FiddleDeDee a b = MkFiddleDeDee a b FiddleDeDee is ``structurally equivalent'' to (,), and also carries about as much information. Consider: ``What's the French for fiddle-de-dee?'' ``Fiddle-de-dee's not English,'' Alice replied gravely. ``Who ever said it was?'' said the Red Queen. Lewis Carroll, ``Through the Looking Glass'' > However, > data D a b = MkD a b > data E a b = MkE a b > (D Int Int) and (E Int Int) are trated as different because of name > equivalency testing. > Basically there are 2 type constructors -> ( , ) with structural > equivalency, which is odd. Someone just dumped some idiosyncracies > of lamda calculus into the language. I assume from your example that by ``structural equivalence'' you mean the relationship between D and E. But they also share that relationship with (,)---what exactly is the difference? Functions over (D Int Int) work even if the caller thinks its (D #apples #oranges) and the function thinks its (D #books #authors). Again, the problem is with Int, not D (or (,)). > Thanks again.

2 1

RE: Counting occurrences question
by Andy Fugard 05 Jun '02

05 Jun '02

>===== Original Message From "xoo" <ixoo21(a)hotmail.com> ===== >hi.. i was just wondering if some body could give a simple equation for the following situation.other than recursion plz.. > >occurrences :: Eq a => a -> [a] -> [a] >--occurrences xs ys returns the number of times that xs occurs in ys You may find it easier if you make occurrences :: Eq a => a -> [a] -> Integer since it would seem it is to return a number, and not another list! Also I would guess the function will have a form something like occurrences x xs = foldr (countOp x) 0 xs where countOp :: Eq a => a -> a -> Integer -> Integer ... I'm not sure if I should go any further, in case this is a homework question... Andy -- [ Andy Fugard ] [ +44 (0)7901 603075 ]

3 3

Bilgisayar Egitiminde Bir Numara
by Sertifikam.Com 05 Jun '02

05 Jun '02

1 0

Bilgisayar Egitiminde Bir Numara
by Sertifikam.Com 05 Jun '02

05 Jun '02

1 0