Specify array or list size?

Daniel Carrera

7 May 2005 7 May '05

9:24 a.m.

Hello, Right now I'm using type declarations like: f :: Int -> [Int] So f returns a list of Ints. Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size. Cheers, Daniel.

Show replies by date

Max Vasin

7 May 7 May

10:18 a.m.

Daniel Carrera writes:

...

Hello,

Right now I'm using type declarations like:

f :: Int -> [Int]

So f returns a list of Ints.

Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size. In short: in type declarations you can't.

But why do you need that? Where do need to make an assumption about the size of the list? -- WBR, Max Vasin.

Daniel Carrera

10:34 a.m.

Max Vasin wrote:

...

But why do you need that? Where do need to make an assumption about the size of the list?

I'm implementing the RC4 algorithm, which requires a state array with 256 elements containing the bytes from 0 to 255. As the algorithm progresses, the elements of the array get shuffled around. This is what drives the pseudo-random number generator. But the size of the state array is always 256. Cheers, Daniel.

Max Vasin

12:05 p.m.

Daniel Carrera writes:

...

Max Vasin wrote:

...
But why do you need that? Where do need to make an assumption about the size of the list?

I'm implementing the RC4 algorithm, which requires a state array with 256 elements containing the bytes from 0 to 255. As the algorithm progresses, the elements of the array get shuffled around. This is what drives the pseudo-random number generator. But the size of the state array is always 256. So, you need list of length 256 and then just use it as state of your PRNG. If you want to check list size you have to do it at runtime:

f lst | length lst == 256 -> doWork | otherwise -> fail "length lst must be 256" -- WBR, Max Vasin.

Daniel Carrera

12:11 p.m.

Max Vasin wrote:

...

So, you need list of length 256 and then just use it as state of your PRNG. If you want to check list size you have to do it at runtime:

f lst | length lst == 256 -> doWork | otherwise -> fail "length lst must be 256"

Okay, thanks. Cheers, Daniel.

Hamilton Richards

11:09 a.m.

At 9:24 AM -0400 2005/5/7, Daniel Carrera wrote:

...

Hello,

Right now I'm using type declarations like:

f :: Int -> [Int]

So f returns a list of Ints.

Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size.

Well, for starters, lists and arrays are two entirely different topics. I've noticed that Haskell newbies sometimes confuse them --possibly the use of [] in list types and enumerations triggers an unconscious association with [] used in conventional languages for array indexing. It's easy to define a function that constructs a list of a given size, but that size is not part of the list's type. As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal, and it turned out to be an unmitigated disaster. Because array parameters were typed with their sizes, a procedure for searching arrays of size 100 could not be used for arrays of any other size. Every useful (non-Standard) dialect of Pascal provided a way around that restriction, as did Pascal's successor, Modula-2, and as far as I know the mistake has not been repeated. As for Haskell arrays, I've been programming in Haskell since the early 1990's, and I've never really needed them. Most Haskell programmers find lists much more useful, and you'd probably be better off concentrating on lists until you encounter a problem in which arrays are really needed. When you do, you'll discover that in Haskell as in most other languages, an array's size is not part of its type. It's nice to see you taking up Haskell with such enthusiasm. If you agree with many of us that Haskell's one of today's best programming programming languages, I hope you'll help spread the word. With best wishes, --Ham -- ------------------------------------------------------------------ Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer The University of Texas at Austin 512-471-9525 1 University Station C0500 Taylor Hall 5.138 Austin, Texas 78712-0233 ham@cs.utexas.edu hrichrds@swbell.net http://www.cs.utexas.edu/users/ham/richards ------------------------------------------------------------------

Daniel Carrera

12:04 p.m.

Hamilton Richards wrote:

...

Well, for starters, lists and arrays are two entirely different topics. I've noticed that Haskell newbies sometimes confuse them --possibly the use of [] in list types and enumerations triggers an unconscious association with [] used in conventional languages for array indexing.

I think it's because there's no real reason for someone to think that the words "list" and "array" might not be synonims. I certainly don't seen a linguistic distinction. Either term refers to an ordered collection of items. Suppose that you learn a new computer language, and it happens to assign special meanings to the words "collection" and "group". You don't know this. So you start talking about groups as you do in every day English and people tell you that you're mixing up concepts. I guess that a more likely example in programming would be a language that differentiates between "functions", "procedures" and "subroutines".

...

As for Haskell arrays, I've been programming in Haskell since the early 1990's, and I've never really needed them. Most Haskell programmers find lists much more useful, and you'd probably be better off concentrating on lists until you encounter a problem in which arrays are really needed.

Arrays have O(1) lookup, and Lists have O(n) lookup. For some purposes, arrays might be better. I'm thinking of reimplementing RC4 with arrays to see if it makes a differece.

...

When you do, you'll discover that in Haskell as in most other languages, an array's size is not part of its type.

Well... that's not quite what I was looking for. I just wanted to raise an error if the array ever has length other than 256. And I don't know how to do that on a language that doesn't have side-effects.

...

It's nice to see you taking up Haskell with such enthusiasm. If you agree with many of us that Haskell's one of today's best programming programming languages, I hope you'll help spread the word.

:-) A lot of concepts from Haskell match the way I think about problems. You see, my background is in math, not programming. For example, currying and higher order functions are essentially new names for things I've been doing for years. So after the concept was explained to me, it didn't take me that long to "get it". My current impression is that Haskell is great for anyone with good mathematics education. But I don't know how it'd fare with other people. I have a lady friend who wants to learn how to program. She's a technical person, but has no math background to speak of. I can't decide whether to start with a clear-syntax imperative language (Ruby) or a functional language (Haskell). I confess I've been leaning towards Ruby. Cheers, Daniel.

Sebastian Sylvan

12:22 p.m.

On 5/7/05, Daniel Carrera wrote:

...

Hamilton Richards wrote:

...
Well, for starters, lists and arrays are two entirely different topics. I've noticed that Haskell newbies sometimes confuse them --possibly the use of [] in list types and enumerations triggers an unconscious association with [] used in conventional languages for array indexing.

I think it's because there's no real reason for someone to think that the words "list" and "array" might not be synonims. I certainly don't seen a linguistic distinction. Either term refers to an ordered collection of items.

Hmm. Not sure I agree. For me an "array" is a fixed set of elements which may or not contain stuff (not necessarily in a CS context but just linguistically). A "list" is more of a linear structure. An array is a sheet of paper with lines on it, a list is the todo-list written on that paper. Anyway. There is a difference, and I think the names reflect that pretty well. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Daniel Carrera

12:36 p.m.

Sebastian Sylvan wrote:

...

Anyway. There is a difference, and I think the names reflect that pretty well.

I'm glad you think that. Sadly, not everyone else does. My take is: sure I can accept that there's a difference once I'm told that there is, but this wasn't evident atll to /me/ from the names. I must also confess that after hearing your explanation I still don't understand the linguistic distinction. I don't see a natural reason why arrays should be slots and lists should be the contents of the slots. And I don't see how that relates to Haskell's distinction. Cheers, Daniel.

Sebastian Sylvan

2:08 p.m.

On 5/7/05, Daniel Carrera wrote: at there is, but this wasn't evident atll to /me/ from the names.

...

I must also confess that after hearing your explanation I still don't understand the linguistic distinction.

Basically, when I see the word "array" I think of a field of cells. It's the structure itself and not the contents. Then, of course, you could use an array to hold a "list of names" or something, but array is still the underlying structure used as a list (or a buffer, at least that's how I think abut it. A "list" is, for me, more of a "logical" entity (as opposed to structural). It's a sequence of "stuff" not a particular way to store it (singly-linked, doubly-linked, arraylists etc.). Anyway, that's just how I naturally "feel" when I hear those two words. Arrays are a monolithic field of memory cells, lists are sequences of values. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Marcin 'Qrczak' Kowalczyk

2:34 p.m.

Sebastian Sylvan writes:

...

A "list" is, for me, more of a "logical" entity (as opposed to structural). It's a sequence of "stuff" not a particular way to store it (singly-linked, doubly-linked, arraylists etc.).

I call it "sequence". A list is usually a concrete type in a given language. Exceptions: Python calls its arrays lists, and Perl calls its sequences lists. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Benjamin Franksen

4:56 p.m.

On Saturday 07 May 2005 18:22, Sebastian Sylvan wrote:

...

On 5/7/05, Daniel Carrera wrote:

...
Hamilton Richards wrote:

...
Well, for starters, lists and arrays are two entirely different topics. I've noticed that Haskell newbies sometimes confuse them --possibly the use of [] in list types and enumerations triggers an unconscious association with [] used in conventional languages for array indexing.

I think it's because there's no real reason for someone to think that the words "list" and "array" might not be synonims. I certainly don't seen a linguistic distinction. Either term refers to an ordered collection of items.

Hmm. Not sure I agree. For me an "array" is a fixed set of elements which may or not contain stuff (not necessarily in a CS context but just linguistically). A "list" is more of a linear structure. An array is a sheet of paper with lines on it, a list is the todo-list written on that paper.

Anyway. There is a difference, and I think the names reflect that pretty well.

I think that 'list' is a misnomer for what are actually (functional) stacks. That these so called lists are used for almost everything is due to (1) the nice syntactic sugar (2) the fact that there are many functions on lists in the standard libraries and (3) they can be infinite and thus act as streams. It would be a great improvement if Haskell's standard library (including the Prelude) would provide a uniform framework for collections, and in particular sequences (linear collections, indexed by natural numbers), and there should be standard implementations that don't favour operations on the left end over those on the right end. It is a shame that a language like Haskell doesn't even have a Deque (double ended queue) in the its standard library. Robert Will has proposed a new unified standard for collections (as well as some default implementations) with above properties (and a lot more). IMHO, his work is (at least) a very good starting point and deserves more attention. Ben

Stefan Monnier

12:31 p.m.

...

I have a lady friend who wants to learn how to program. She's a technical person, but has no math background to speak of. I can't decide whether to start with a clear-syntax imperative language (Ruby) or a functional language (Haskell). I confess I've been leaning towards Ruby.

In my limited experience it's easier to learn an imperative language after a functional one than the reverse. So I'd recommend she start with Haskell. It's actually easy to learn if you haven't been lobotomized by Java/C/C++. Stefan

Daniel Carrera

12:40 p.m.

Stefan Monnier wrote:

...

...
I have a lady friend who wants to learn how to program. She's a technical person, but has no math background to speak of. I can't decide whether to start with a clear-syntax imperative language (Ruby) or a functional language (Haskell). I confess I've been leaning towards Ruby.

In my limited experience it's easier to learn an imperative language after a functional one than the reverse. So I'd recommend she start with Haskell. It's actually easy to learn if you haven't been lobotomized by Java/C/C++.

:-) Maybe that's why I like it so far. I haven't been corrupted yet :-) I don't know Java. I glanced at C++ and decided I don't want it. I like C, but I program it at an amateurish level. I'll keep your thoughts in mind. In your opinion, do you think Haskell is appropriate for someone with zero math background? I can't imagine how I'd explain something like currying to someone who doesn't know math. Cheers, Daniel.

David Roundy

1:08 p.m.

On Sat, May 07, 2005 at 12:40:55PM -0400, Daniel Carrera wrote:

...

In your opinion, do you think Haskell is appropriate for someone with zero math background? I can't imagine how I'd explain something like currying to someone who doesn't know math.

I'd think it'd be pretty easy for a non-mathy non-programmer person to learn (based on pure speculation--I've never taught haskell). There is a sort of "basic core" of haskell that is pretty easy, and most of the higher level concepts are a sort of nicer way to say the same thing. For example, while lambda expressions are very nice, it's always possible to do the same thing by declaring a named function in a let or where clause. -- David Roundy http://www.darcs.net

Graham Klyne

9 May 9 May

6:45 a.m.

New subject: Haskell for non-mathematicians (was: Specify array or list size?)

At 13:08 07/05/05 -0400, David Roundy wrote:

...

On Sat, May 07, 2005 at 12:40:55PM -0400, Daniel Carrera wrote:

...
In your opinion, do you think Haskell is appropriate for someone with zero math background? I can't imagine how I'd explain something like currying to someone who doesn't know math.

I'd think it'd be pretty easy for a non-mathy non-programmer person to learn (based on pure speculation--I've never taught haskell). There is a sort of "basic core" of haskell that is pretty easy, and most of the higher level concepts are a sort of nicer way to say the same thing. For example, while lambda expressions are very nice, it's always possible to do the same thing by declaring a named function in a let or where clause.

I'm reminded of something mentioned by Alan Kay in a recent interview published in ACM Queue magazine: [[ AK [...] One of the things that people realized from these extensible languages is that there is the unfortunate difficulty of making the meta-system easy to use. Smalltalk-72 was actually used by children. Youre always extending the language without realizing it when you are making ordinary classes. The result of this was that you didnt have to go into a more esoteric place like a compiler compilerYacc or something like thatto add some extension to the language. But the flip side of the coin was that even good programmers and language designers tended to do terrible extensions when they were in the heat of programming, because design is something that is best done slowly and carefully. SF And late-night extensible programming is unsupportable. AK Exactly. So Smalltalk actually went from something that was completely extensible to one where we picked a syntax that allowed for a variety of forms of what was fixed, and concentrated on the extensibility of meaning in it. This is not completely satisfactory. One of the things that I think should be done today is to have a fence that you have to hop to forcibly remind you that youre now in a meta-areathat you are now tinkering with the currency system itself, you are not just speculating. But it should allow you to do it without any other overhead once youve crossed this fence, because when you want to do it, you want to do it. ]] -- http://www.acmqueue.com/modules.php?name=Content&pa=showpage&pid=273 When I read the above, I found myself thinking of two styles of Haskell programming: on one hand there are some, many on these mailing lists, but I pick Oleg as an exemplar, who continue to baffle me with the amazing tricks they can do with (say) the Haskell type system. And there are "ordinary programmers" (like myself) who want to use Haskell's small core and (not-so-small) type system to find more elegant ways to write application software (e.g. http://www.cs.kent.ac.uk/projects/vital/ - if IO were added). I find that higher order functions and currying provide powerful tools to isolate different aspects of a program's functionality, but I'm not sure I'd want to explain them to a complete novice programmer. So, responding to the original comment, I think there's a core of Haskell that's probably quite suitable for non-mathematical programmers, but there's a lot of potential to build application frameworks that requires a mathematical kind of abstract and analytical approach, if not specifically a mathematical background. A challenge that I think a little about, sometimes, is how to keep them distinct, which is a point to which Alan Kay seems to be alluding (above). #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

Bulat Ziganshin

10 May 10 May

6:19 a.m.

New subject: Haskell for non-mathematicians (was: Specify array or list size?)

Hello Graham, Monday, May 09, 2005, 2:45:06 PM, you wrote: GK> When I read the above, I found myself thinking of two styles of Haskell GK> programming: on one hand there are some, many on these mailing lists, but GK> I pick Oleg as an exemplar, who continue to baffle me with the amazing GK> tricks they can do with (say) the Haskell type system. And there are GK> "ordinary programmers" (like myself) who want to use Haskell's small core GK> and (not-so-small) type system to find more elegant ways to write GK> application software (e.g. http://www.cs.kent.ac.uk/projects/vital/ - if IO GK> were added). I find that higher order functions and currying provide GK> powerful tools to isolate different aspects of a program's functionality, GK> but I'm not sure I'd want to explain them to a complete novice programmer. imho, this theoretical foundations of Haskell power just don't need to be explained explicitly. Haskell function just can be applied to part of its argumnets and we use this very often. small and easy to understand example are "add2 = map (+2)" which at the same time use parially-applied function and return such function. it's a problem of other languages advocates to explain how partial application can be emulated in their ugly languages :) and about selecting first language to teach programming. if one needs to learn concept of controlling computer with help of programmng language, it's better imho to use dynamic language with minimum declarations, such as Ruby (or even Logo :) I think that runtime error messages given in terms of VALUES instead of compile-time error messages given in terms of TYPES are easier to understand for novice. also, strict regulations on datatypes are needed for professional program development, but will be just needless complication for learning concept of programming itself. even for mathematician Ruby will be a good choice on the other side, to learn DISCIPLINE of programming, Haskell with all its strictness will be a very good instrument in the old times the same way Pascal was used to teaching future programmers and Basic for all others -- Best regards, Bulat mailto:bulatz@HotPOP.com

Sebastian Sylvan

12:39 p.m.

New subject: Haskell for non-mathematicians (was: Specify array or list size?)

On 5/10/05, Bulat Ziganshin wrote: I think that runtime error

...

messages given in terms of VALUES instead of compile-time error messages given in terms of TYPES are easier to understand for novice. also, strict regulations on datatypes are needed for professional program development, but will be just needless complication for learning concept of programming itself. even for mathematician Ruby will be a good choice

I disagree. Types is a very important concept and I think that should be emphasized in the first lecture. If one goes through types _and_ values from the very beginning a strongly typed language will be of the same aid to beginners as it is to experts. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Bulat Ziganshin

1:40 p.m.

New subject: Re[2]: Haskell for non-mathematicians (was: Specify array or list size?)

Hello Sebastian, Tuesday, May 10, 2005, 8:39:23 PM, you wrote: SS> I think that runtime error

...

...
messages given in terms of VALUES instead of compile-time error messages given in terms of TYPES are easier to understand for novice. also, strict regulations on datatypes are needed for professional program development, but will be just needless complication for learning concept of programming itself. even for mathematician Ruby will be a good choice

SS> I disagree. SS> Types is a very important concept and I think that should be SS> emphasized in the first lecture. If one goes through types _and_ SS> values from the very beginning a strongly typed language will be of SS> the same aid to beginners as it is to experts. imvho, exposing types to non-professionals is like exposing light theory to a kid which just want to draw a picture. values are just enough to these peoples -- Best regards, Bulat mailto:bulatz@HotPOP.com

karczma＠info.unicaen.fr

2 p.m.

New subject: Haskell for non-mathematicians (was: Specify array or list size?)

Bulat Ziganshin discusses with SS:

...

SS> Types is a very important concept and I think that should be SS> emphasized in the first lecture. If one goes through types _and_ SS> values from the very beginning a strongly typed language will be of SS> the same aid to beginners as it is to experts.

imvho, exposing types to non-professionals is like exposing light theory to a kid which just want to draw a picture. values are just enough to these peoples

No, I am sorry, I disagree rather strongly. I taught programming to fresh undergraduates, and a little bit, occasionally to secondary school folk. We used Scheme. I taught also some programming to biology students, using Python. (Biology students are very resistant to all kind of mathe- matical reasoning...) So, as you see, we used dynamically typed languages. First bugs the students/pupils see, after having mastered the syntax are type errors. Presented as such. "sin expects a float". or " ... of type <number>". Hiding the typing at this level is a crime, it prevents them from understanding what is the essence of their bugs. I was OBLIGED to discuss types quite early, and everybody was satisfied. I am afraid that your claim is not based on experience. Jerzy Karczmarczuk

Sebastian Sylvan

3:25 p.m.

New subject: Re[2]: Haskell for non-mathematicians (was: Specify array or list size?)

On 5/10/05, Bulat Ziganshin wrote:

...

Hello Sebastian,

Tuesday, May 10, 2005, 8:39:23 PM, you wrote:

SS> I think that runtime error

...
...
messages given in terms of VALUES instead of compile-time error messages given in terms of TYPES are easier to understand for novice. also, strict regulations on datatypes are needed for professional program development, but will be just needless complication for learning concept of programming itself. even for mathematician Ruby will be a good choice

SS> I disagree. SS> Types is a very important concept and I think that should be SS> emphasized in the first lecture. If one goes through types _and_ SS> values from the very beginning a strongly typed language will be of SS> the same aid to beginners as it is to experts.

imvho, exposing types to non-professionals is like exposing light theory to a kid which just want to draw a picture. values are just enough to these peoples

Why? A value has a type, that's very natural and also important. It's more like teaching someone who wants to paint what types of paint exist and how they work together. I strongly oppose the idea that one should hide fundamental concepts to newbies, I think that will lead to extreme difficulties later on. Even in untyped languages you need a concept of types. You WILL need to say something like "'apple + 5' won't work because they have different _types_ of values", so why not use a language which enforces this concept in practice? I think it's better to enforce things like this to the newbie, once they have a good understanding of types _then_ they might be able to use an untyped language responsibly, but until they do I think it's fine for the compiler to instruct them when they make a misstake instead of simply getting some weird runtime error. You don't need to expose some of the more advanced type-system hacks, but simply ignoring something so fundamental such as types is in my opinion not very helpful. I really see no validity in the standpoint that untyped languages are better to teach to the newbie. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Sebastian Sylvan

7 May 7 May

2:12 p.m.

On 5/7/05, Daniel Carrera wrote:

...

Stefan Monnier wrote:

...
...
I have a lady friend who wants to learn how to program. She's a technical person, but has no math background to speak of. I can't decide whether to start with a clear-syntax imperative language (Ruby) or a functional language (Haskell). I confess I've been leaning towards Ruby.

In my limited experience it's easier to learn an imperative language after a functional one than the reverse. So I'd recommend she start with Haskell. It's actually easy to learn if you haven't been lobotomized by Java/C/C++.

:-)

Maybe that's why I like it so far. I haven't been corrupted yet :-) I don't know Java. I glanced at C++ and decided I don't want it. I like C, but I program it at an amateurish level.

I'll keep your thoughts in mind.

In your opinion, do you think Haskell is appropriate for someone with zero math background? I can't imagine how I'd explain something like currying to someone who doesn't know math.

I have some experience teaching Haskell (TA) and I am too of the opinion that FP is a lot easier to learn than imperative programming if you have zero programming background. However, if you've warped your mind enough to actually "think" imperatively when solving problems (by years of C programming, for instance), you may have trouble unlearning that before you can really get effective with FP. Also, math is no prerequisite if you ask me. The concepts in FP are natural and straight-forward, and so is (most) math. You could just as easily learn math by programming Haskell as learning Haskell by doing math. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Antti-Juhani Kaijanaho

3:11 p.m.

On 20050507T120430-0400, Daniel Carrera wrote:

...

I think it's because there's no real reason for someone to think that the words "list" and "array" might not be synonims. I certainly don't seen a linguistic distinction. Either term refers to an ordered collection of items.

I don't even know what "array" means outside of programming (but then again, English is not my native language). However... It is dangerous for anyone to infer the meaning of a technical term based on the common meaning of the word. The common meaning usually helps in *remembering* the technical meaning, but that comes *after* finding out what the technical meaning is. This applies in any technology or science, not just Haskell programming or programming in general.

...

Suppose that you learn a new computer language, and it happens to assign special meanings to the words "collection" and "group".

Those terms have a lot of meanings in technical jargon.

...

You don't know this. So you start talking about groups as you do in every day English and people tell you that you're mixing up concepts.

Your mistake is the "start talking about groups as you do in every day English" part.

...

I guess that a more likely example in programming would be a language that differentiates between "functions", "procedures" and "subroutines".

Well, most languages use "function" contrary to the everyday meaning of the word. Even "functional" in "functional programming" does not mean what you'd think it means. (Anybody else heard people shout "But C *is* a functional language!"? - And I'm not talking about geeks who use the FP style in C:) -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Daniel Carrera

3:17 p.m.

Antti-Juhani Kaijanaho wrote:

...

Your mistake is the "start talking about groups as you do in every day English" part.

The point I'm trying to make is that you can't necessarily predict that a programming language will abscribe special meaning to standard known words like "group" or "list". I can very well talk about a list without knowing that the members of this list (see?) might have a special meaning for that word that I'm not aware of. You can't possibly forsee that sort of thing. It is not a mistake to use the word "group" to mean what it means in English, I can't possibly know that an Algebraist has a particular definition of "group" that differs from every-day use. Cheers, Daniel.

Antti-Juhani Kaijanaho

3:43 p.m.

On 20050507T151723-0400, Daniel Carrera wrote:

...

Antti-Juhani Kaijanaho wrote:

...
Your mistake is the "start talking about groups as you do in every day English" part.

The point I'm trying to make is that you can't necessarily predict that a programming language will abscribe special meaning to standard known words like "group" or "list".

*My* point is that if you have any experience with any technological or science topic, you'll know that terms tend to have specialized meanings in jargons, and you'll know to look for it.

...

I can very well talk about a list without knowing that the members of this list (see?) might have a special meaning for that word that I'm not aware of. You can't possibly forsee that sort of thing.

Yes you can. You can't foresee the particular case, but you can think ahead and *expect* to find a specialized meaning.

...

I can't possibly know that an Algebraist has a particular definition of "group" that differs from every-day use.

No, but you can make a fair guess that whatever the definition is, it does not match everyday use. -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Fergus Henderson

12:36 p.m.

On 07-May-2005, Hamilton Richards wrote:

...

As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal,

There have been many such languages since Standard Pascal. For example C, C++, C#, Java, Ada, VHDL, and NU-Prolog.

...

and it turned out to be an unmitigated disaster. Because array parameters were typed with their sizes, a procedure for searching arrays of size 100 could not be used for arrays of any other size. Every useful (non-Standard) dialect of Pascal provided a way around that restriction, as did Pascal's successor, Modula-2, and as far as I know the mistake has not been repeated.

The disaster was the lack of polymorphism in Pascal's type system, not making array sizes part of their types. The languages above all have some means of writing a procedure that works for different sized arrays, whether it be using pointers (in C), templates (in C++), unconstrained array parameters (in Ada and VHDL), or inheritence (in C# and Java). Another example of a programming language for which array lengths are part of their type is Cryptol . Cryptol was designed by Galois Connections, the company that I work for, starting about five years ago (i.e. before I joined Galois). It is notable in this context because it was designed by expert functional programmers who were very familiar with Haskell, and who had indeed participated in the design and implementation of Haskell. They chose to include array sizes in the type system, despite the resulting increase in the complexity of the type system, because array sizes are often important for the domain of cryptography -- as the original poster noticed! -- Fergus J. Henderson | "I have always known that the pursuit Galois Connections, Inc. | of excellence is a lethal habit" Phone: +1 503 626 6616 | -- the last words of T. S. Garp.

Antti-Juhani Kaijanaho

1:36 p.m.

On 20050507T093613-0700, Fergus Henderson wrote:

...

On 07-May-2005, Hamilton Richards wrote:

...
As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal,

There have been many such languages since Standard Pascal. For example C, C++, C#, Java, Ada, VHDL, and NU-Prolog.

C, C++ and Java do not belong to that list. I can't speak about the others, not being very familiar with them. In C and C++, the declaration int n[50]; introduces an array variable with size 50 having the type "array of int". The size is *not* part of the type. In Java, the array size is not given in the declaration at all (instead, it is given in the new expression), and is not part of the type. -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Marcin 'Qrczak' Kowalczyk

2:32 p.m.

Antti-Juhani Kaijanaho writes:

...

...
...
As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal,

There have been many such languages since Standard Pascal. For example C, C++, C#, Java, Ada, VHDL, and NU-Prolog.

C, C++ and Java do not belong to that list. I can't speak about the others, not being very familiar with them.

Java and C# don't belong to that list, but C and C++ do. I don't know about others.

...

In C and C++, the declaration int n[50]; introduces an array variable with size 50 having the type "array of int". The size is *not* part of the type.

No, it introduces a variable of type "array of 50 ints", which can be converted to "pointer to int". It matters when you make a pointer of such arrays, an array of such arrays, or sizeof such array. In C++ the size can be matched by template parameter, and you can have separate overloadings for separate array sizes. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Thomas Davie

2:49 p.m.

...

No, it introduces a variable of type "array of 50 ints", which can be converted to "pointer to int".

It matters when you make a pointer of such arrays, an array of such arrays, or sizeof such array. In C++ the size can be matched by template parameter, and you can have separate overloadings for separate array sizes.

I'm not familiar with your C++ example (not being familiar with C++), but I think that it's a bit of a stretch of the imagination to say that C "introduces a variable of type "array of 50 ints"", the fact that this is now an array of 50 integers is never checked at any point in the compilation or run, and I'm not sure it can be even if K&R had wanted to. If I'm thinking straight then *any* array definition merely gets re-written to a memory allocation of the relevant amount of ram, and beyond this point it is forever of type "pointer to <array content type>". As an example: int bobsArray[5]; bobsArray[6] = 23; is not badly typed – it is merely a badly broken program. Bob

Jacob Nelson

3:04 p.m.

GCC knows how big an array is: jake$ cat > arrsizetest.c #include int main() { int a[50]; printf("sizeof a == %d\n",sizeof(a)); return 0; } jake$ gcc arrsizetest.c jake$ ./a.out sizeof a == 200 jacob On Sat, 7 May 2005, Thomas Davie wrote:

...

...
No, it introduces a variable of type "array of 50 ints", which can be converted to "pointer to int".

It matters when you make a pointer of such arrays, an array of such arrays, or sizeof such array. In C++ the size can be matched by template parameter, and you can have separate overloadings for separate array sizes.

I'm not familiar with your C++ example (not being familiar with C++), but I think that it's a bit of a stretch of the imagination to say that C "introduces a variable of type "array of 50 ints"", the fact that this is now an array of 50 integers is never checked at any point in the compilation or run, and I'm not sure it can be even if K&R had wanted to. If I'm thinking straight then *any* array definition merely gets re-written to a memory allocation of the relevant amount of ram, and beyond this point it is forever of type "pointer to <array content type>".

As an example:

int bobsArray[5]; bobsArray[6] = 23;

is not badly typed ? it is merely a badly broken program.

Bob _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Abraham Egnor

3:12 p.m.

On 5/7/05, Jacob Nelson wrote:

...

GCC knows how big an array is:

jake$ cat > arrsizetest.c #include

int main() { int a[50]; printf("sizeof a == %d\n",sizeof(a)); return 0; } jake$ gcc arrsizetest.c jake$ ./a.out sizeof a == 200

So does ghc: import Data.Array main = let a = listArray (0, 49) $ replicate 50 0 in putStrLn $ "array size == " ++ show (rangeSize $ bounds a) [abe@catspaw:~/src/test/haskell] $ runghc arrsize.hs array size == 50 That doesn't mean the size is part of the *type*. Abe

Jacob Nelson

3:31 p.m.

On Sat, 7 May 2005, Abraham Egnor wrote:

...

So does ghc: ... That doesn't mean the size is part of the *type*.

Sure. I'm just pointing out that int a[50]; is not *quite* the same as int *a = (int *)malloc(50 * sizeof(int)); jacob

Hamilton Richards

4:25 p.m.

At 12:04 PM -0700 2005/5/7, Jacob Nelson wrote:

...

GCC knows how big an array is:

jake$ cat > arrsizetest.c #include

int main() { int a[50]; printf("sizeof a == %d\n",sizeof(a)); return 0; } jake$ gcc arrsizetest.c jake$ ./a.out sizeof a == 200

jacob

gcc knows the size of an array variable only in the scope of its definition: #include void f( int x[] ) { printf("f: sizeof a == %d\n",sizeof(x)); } int main() { int a[50]; printf("main: sizeof a == %d\n",sizeof(a)); f( a ); return 0; } ham% gcc arrsize.c ham% a.out main: sizeof a == 200 f: sizeof a == 4 Cheers, --Ham

Marcin 'Qrczak' Kowalczyk

3:07 p.m.

Thomas Davie writes:

...

I'm not familiar with your C++ example (not being familiar with C++), but I think that it's a bit of a stretch of the imagination to say that C "introduces a variable of type "array of 50 ints"", the fact that this is now an array of 50 integers is never checked at any point in the compilation or run, and I'm not sure it can be even if K&R had wanted to.

The size is taken into account when such array type is an element of another array, and by sizeof. int (*p)[50]; /* p may legally point only to arrays of 50 ints each */ ++p; /* p is assumed to point into an array, and is moved by one element, i.e. by 50 ints */

...

As an example:

int bobsArray[5]; bobsArray[6] = 23;

is not badly typed - it is merely a badly broken program.

Because the array size is not taken into account by indexing. But it's a part of the type. These issues are independent, for example in C# both are the opposite. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Thomas Davie

3:20 p.m.

On May 7, 2005, at 8:07 PM, Marcin 'Qrczak' Kowalczyk wrote:

...

Thomas Davie writes:

...
I'm not familiar with your C++ example (not being familiar with C++), but I think that it's a bit of a stretch of the imagination to say that C "introduces a variable of type "array of 50 ints"", the fact that this is now an array of 50 integers is never checked at any point in the compilation or run, and I'm not sure it can be even if K&R had wanted to.

The size is taken into account when such array type is an element of another array, and by sizeof.

int (*p)[50]; /* p may legally point only to arrays of 50 ints each */ ++p; /* p is assumed to point into an array, and is moved by one element, i.e. by 50 ints */ I'm not sure what you're trying to prove by saying that... There is still no type information that says that the contents of p are an array of 50 elements... I can still attempt to access element 51 and get a runtime memory error. The type of p is still int**, not "pointer to array of 50 ints"

...

...
As an example:

int bobsArray[5]; bobsArray[6] = 23;

is not badly typed - it is merely a badly broken program.

Because the array size is not taken into account by indexing. But it's a part of the type. These issues are independent, for example in C# both are the opposite. I don't think it is part of the type... Does the compiler ever know any more about the type of bobsArray other than it's a pointer to an integer? I think that the above code can be directly translated to:

int *bobsArray; bobsArray = (int *)malloc(5 * sizeof(int)); bobsArray[6] = 23 Which stores exactly the same about on type information. Bob

David Roundy

3:31 p.m.

On Sat, May 07, 2005 at 08:20:15PM +0100, Thomas Davie wrote:

...

On May 7, 2005, at 8:07 PM, Marcin 'Qrczak' Kowalczyk wrote:

...
The size is taken into account when such array type is an element of another array, and by sizeof.

int (*p)[50]; /* p may legally point only to arrays of 50 ints each */ ++p; /* p is assumed to point into an array, and is moved by one element, i.e. by 50 ints */

I'm not sure what you're trying to prove by saying that... There is still no type information that says that the contents of p are an array of 50 elements... I can still attempt to access element 51 and get a runtime memory error. The type of p is still int**, not "pointer to array of 50 ints"

No, int (*p)[50] is a multidimensional array, one of the most useless concepts in C, and is equivalent to int p[50][] (or is it p[][50]... I always get my matrix subscripts messed up). In a multi-dimensional array, all the dimensions but the first (or last?) are fixed in size. Unfortunately, these are fixed at compile time, so there's no way to write a function that can act upon multidimensional arrays of arbitrary size. So we get the joy of writing terms like m[i+n*j] to deal with matrices... -- David Roundy http://www.darcs.net

Thomas Davie

3:41 p.m.

On May 7, 2005, at 8:31 PM, David Roundy wrote:

...

On Sat, May 07, 2005 at 08:20:15PM +0100, Thomas Davie wrote:

...
On May 7, 2005, at 8:07 PM, Marcin 'Qrczak' Kowalczyk wrote:

...
The size is taken into account when such array type is an element of another array, and by sizeof.

int (*p)[50]; /* p may legally point only to arrays of 50 ints each */ ++p; /* p is assumed to point into an array, and is moved by one element, i.e. by 50 ints */

I'm not sure what you're trying to prove by saying that... There is still no type information that says that the contents of p are an array of 50 elements... I can still attempt to access element 51 and get a runtime memory error. The type of p is still int**, not "pointer to array of 50 ints"

No, int (*p)[50] is a multidimensional array, one of the most useless concepts in C, and is equivalent to int p[50][] (or is it p[][50]... I always get my matrix subscripts messed up).

In a multi-dimensional array, all the dimensions but the first (or last?) are fixed in size. Unfortunately, these are fixed at compile time, so there's no way to write a function that can act upon multidimensional arrays of arbitrary size. So we get the joy of writing terms like m [i+n*j] to deal with matrices... :o It appears I have grossly underestimated how much C checks at compile time... I still feel all warm and cuddly in the everything checked world of Haskell though. And with that... I wonder, is this topic perhaps diverging from discussing how to get list sizes checked with Haskell's type checker and moving onto something relatively irrelevant.

Bob

Marcin 'Qrczak' Kowalczyk

3:49 p.m.

David Roundy writes:

...

No, int (*p)[50] is a multidimensional array, one of the most useless concepts in C, and is equivalent to int p[50][] (or is it p[][50]... I always get my matrix subscripts messed up).

No, it's not equivalent to either. Array type are not the same as pointer type. (Except that in function parameters an array type really means a pointer.) int p[50][] is an error because array element type must be a complete type, and an array without a dimension is an incomplete type. int p[][50] declares p as an array with unknown size, of arrays of size 50. Such declaration makes sense: 1. as a declaration of an array defined elsewhere (usually with "extern"); it must have a size specified in some place; 2. with an initializer in braces, whose size determines the array size; 3. as function parameter, where it means a pointer. int (*p)[50] declares p as a pointer to an array of size 50. Such declaration can be used anywhere without restrictions - this is a complete type. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Antti-Juhani Kaijanaho

3:52 p.m.

On 20050507T153105-0400, David Roundy wrote:

...

In a multi-dimensional array, all the dimensions but the first (or last?) are fixed in size. Unfortunately, these are fixed at compile time, so there's no way to write a function that can act upon multidimensional arrays of arbitrary size. So we get the joy of writing terms like m[i+n*j] to deal with matrices...

In C99, you can use variable-length arrays for that, though compiler support for that feature is lacking (in particular, GCC still gets VLAs wrong). -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Glynn Clements

8 May 8 May

6:44 a.m.

Thomas Davie wrote:

...

...
...
I'm not familiar with your C++ example (not being familiar with C++), but I think that it's a bit of a stretch of the imagination to say that C "introduces a variable of type "array of 50 ints"", the fact that this is now an array of 50 integers is never checked at any point in the compilation or run, and I'm not sure it can be even if K&R had wanted to.

The size is taken into account when such array type is an element of another array, and by sizeof.

int (*p)[50]; /* p may legally point only to arrays of 50 ints each */ ++p; /* p is assumed to point into an array, and is moved by one element, i.e. by 50 ints */ I'm not sure what you're trying to prove by saying that... There is still no type information that says that the contents of p are an array of 50 elements...

Put it this way, then: 1 void foo(void) 2 { 3 int a[2][50]; 4 int b[2][60]; 5 int (*p)[50]; 6 7 p = a; 8 p = b; } $ gcc -c -Wall foo.c foo.c: In function `foo': foo.c:8: warning: assignment from incompatible pointer type In line 7, an expression of type "int (*)[50]" is assigned to a variable of type "int (*)[50]", which is OK. In line 8, an expression of type "int (*)[60]" is assigned to a variable of type "int (*)[50]", and the compiler complains.

...

I can still attempt to access element 51 and get a runtime memory error.

That's because C doesn't do bounds checking on array accesses. It has nothing to do with types.

...

The type of p is still int**,

No it isn't. "int**" and "int (*)[50]" are different types and have different run-time behaviour.

...

not "pointer to array of 50 ints"

Yes it is. The semantics of C pointer arithmetic mean that the size of the target is an essential part of the pointer type. In C, arrays and pointers are *not* the same thing. They are often confused because C does several automatic conversions: 1. When used as an expression (rather than an lvalue), arrays are automatically converted to pointers. Arrays only ever occur as lvalues, never as expressions. 2. In a declaration, the x[...] syntax indicates that x is an array, but in an expression, x must be a pointer (which includes an array which has been converted to a pointer due to rule 1 above). 3. When declaring function arguments, you can use "T x[]" or "T x[N]" as an alternative syntax for "T *x"; x is still a pointer, regardless of the syntax used. -- Glynn Clements

Antti-Juhani Kaijanaho

7 May 7 May

3:03 p.m.

On 20050507T203246+0200, Marcin 'Qrczak' Kowalczyk wrote:

...

...
In C and C++, the declaration int n[50]; introduces an array variable with size 50 having the type "array of int". The size is *not* part of the type.

No, it introduces a variable of type "array of 50 ints", which can be converted to "pointer to int".

ISO 9899:1999 (C99) section 6.7.5.2:3 says that its type is "array of int", not "array of 50 ints": If, in the declaration ``T D1'', D1 has one of the forms: D[ type-qualifier-listopt assignment-expressionopt ] D[ static type-qualifier-listopt assignment-expression ] D[ type-qualifier-list static assignment-expression ] D[ type-qualifier-listopt * ] and the type specified for ident in the declaration ``T D'' is `` derived-declarator-type-list T '', then the type specified for ident is ``derived-declarator-type-list array of T ''.121) (See 6.7.5.3 for the meaning of the optional type qualifiers and the keyword static.) 121) When several ``array of'' specifications are adjacent, a multidimensional array is declared.

...

It matters when you make a pointer of such arrays, an array of such arrays, or sizeof such array. In C++ the size can be matched by template parameter, and you can have separate overloadings for separate array sizes.

For C, in all those cases, the array size is a property of the variable, not of the type. -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Marcin 'Qrczak' Kowalczyk

3:28 p.m.

Antti-Juhani Kaijanaho writes:

...

...
No, it introduces a variable of type "array of 50 ints", which can be converted to "pointer to int".

ISO 9899:1999 (C99) section 6.7.5.2:3 says that its type is "array of int", not "array of 50 ints":

Ok, so in C terminology "type" is different from most statically typed languages in this respect. The dimension is used together with the type to determine static properties, and 6.7.5.2:4 says: [#4] For two array types to be compatible, both shall have compatible element types, and if both size specifiers are present, and are integer constant expressions, then both size specifiers shall have the same constant value. If the two array types are used in a context which requires them to be compatible, it is undefined behavior if the two size specifiers evaluate to unequal values. In C++ the size is considered a part of the type: 8.3.4 Arrays [dcl.array] 1 In a declaration T D where D has the form D1 [constant-expressionopt] and the type of the identifier in the declaration T D1 is "derived- declarator-type-list T," then the type of the identifier of D is an array type. T is called the array element type; this type shall not be a reference type, the type void, a function type or an abstract class type. If the constant-expression (_expr.const_) is present, it shall be an integral constant expression and its value shall be greater than zero. The constant expression specifies the bound of (number of elements in) the array. If the value of the constant expression is N, the array has N elements numbered 0 to N-1, and the type of the identifier of D is "derived-declarator-type-list array of N T." In both languages lvalueness is also not considered a part of the type but an alternative language presentation could use a wording where it is. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Antti-Juhani Kaijanaho

3:56 p.m.

On 20050507T212832+0200, Marcin 'Qrczak' Kowalczyk wrote:

...

...
ISO 9899:1999 (C99) section 6.7.5.2:3 says that its type is "array of int", not "array of 50 ints":

Ok, so in C terminology "type" is different from most statically typed languages in this respect. The dimension is used together with the type to determine static properties, and 6.7.5.2:4 says:

[#4] For two array types to be compatible, both shall have

Actually, that's 6.7.5.2:6. It is the only place where array size is truly used as part of the type. In all other contexts, it is easily interpretable as a property of the variable, and since the size of the array is not otherwise used as a type attribute, it is fair to say that it is not really a type attribute. (Not in the Pascal sense, in any case.)

...

In both languages lvalueness is also not considered a part of the type but an alternative language presentation could use a wording where it is.

There are always alternative ways to present a language. -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/

Hamilton Richards

4 p.m.

At 9:36 AM -0700 2005/5/7, Fergus Henderson wrote:

...

On 07-May-2005, Hamilton Richards wrote:

...
As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal,

There have been many such languages since Standard Pascal. For example C, C++, C#, Java, Ada, VHDL, and NU-Prolog.

Well, perhaps we're using the terminology in somewhat different ways. When I say that Standard Pascal includes arrays' sizes in their type, I mean that in Pascal these two arrays: X : array [1..50] of integer; Y : array [1..100] of integer; belong to different types. If I define two procedures procedure P( a : array [1..50] of integer ) procedure Q( a : array [1..100] of integer ) then the calls P( X ) Q( Y ) are valid, but P( Y ) Q( X ) are invalid. That's not the case in C, C++, Java, or Ada. In C and C++, for example, given two arrays int X[50]; int Y[100]; and a function declared as void P( int a[] ) then these calls P( X ) P( Y ) are both valid, because the sizes of X and Y are not part of their type.

...

...
and it turned out to be an unmitigated disaster. Because array parameters were typed with their sizes, a procedure for searching arrays of size 100 could not be used for arrays of any other size. Every useful (non-Standard) dialect of Pascal provided a way around that restriction, as did Pascal's successor, Modula-2, and as far as I know the mistake has not been repeated.

The disaster was the lack of polymorphism in Pascal's type system, not making array sizes part of their types.

Polymorphism would certainly have improved Pascal's type system, but that's a far bigger leap than simply separating arrays' sizes from their types (as was done in Modula-2).

...

The languages above all have some means of writing a procedure that works for different sized arrays, whether it be using pointers (in C), templates (in C++), unconstrained array parameters (in Ada and VHDL), or inheritence (in C# and Java).

As my C/C++ example above shows, in those languages at least, no such special "means" is necessary. In C and C++, there's not even any way for a function to discover the size of an array argument. This is the opposite extreme from Pascal, where the size is determined by the parameter type. Between these extremes is Modula-2, which allows array arguments of any size to be bound to an "open" array parameter, but provides a primitive function HIGH which, applied to an array parameter, returns the size of the argument to which it is bound.

...

Another example of a programming language for which array lengths are part of their type is Cryptol . Cryptol was designed by Galois Connections, the company that I work for, starting about five years ago (i.e. before I joined Galois). It is notable in this context because it was designed by expert functional programmers who were very familiar with Haskell, and who had indeed participated in the design and implementation of Haskell. They chose to include array sizes in the type system, despite the resulting increase in the complexity of the type system, because array sizes are often important for the domain of cryptography -- as the original poster noticed!

Thanks for the pointer-- I had not encountered Cryptol. Looks quite interesting, and I can readily see how making the size of a sequence part of its type can be useful. But it's one thing to make this a feature of a language specific to a domain in which it is useful, or to provide ways to define size-specific array types in a language such as C++, and quite something else to make size-typed arrays the only array types in what was intended to be a general-purpose programming language. That, I still maintain, was a mistake. Cheers, --Ham -- ------------------------------------------------------------------ Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer The University of Texas at Austin 512-471-9525 1 University Station C0500 Taylor Hall 5.138 Austin, Texas 78712-0233 ham@cs.utexas.edu hrichrds@swbell.net http://www.cs.utexas.edu/users/ham/richards ------------------------------------------------------------------

Marcin 'Qrczak' Kowalczyk

4:09 p.m.

Hamilton Richards writes:

...

That's not the case in C, C++, Java, or Ada. In C and C++, for example, given two arrays

int X[50]; int Y[100];

and a function declared as

void P( int a[] )

then these calls

P( X ) P( Y )

are both valid, because the sizes of X and Y are not part of their type.

But here you don't pass the array but a pointer to its first element. You can even call P(&x) where x is an int, not an array at all. Consider this: int X[50]; int Y[100]; void P(int (&a)[50]) {} int main() { P(X); // valid P(Y); // invalid }

...

In C and C++, there's not even any way for a function to discover the size of an array argument.

template<int N> int size(int (&a)[N]) { return N; } -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

Shae Matijs Erisson

12:52 p.m.

New subject: Type System Trix was Re: Specify array or list size?

Daniel Carrera writes:

...

Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size.

Yes, you can build lists with a maximum size. The simplest approach I've seen is BoundedList.hs in the HaskellDB library: http://cvs.sourceforge.net/viewcvs.py/haskelldb/haskelldb/src/Database/Haske... The more general question is, "How to encode values into types in such a way that I can use them?" One neat answer is here: http://pobox.com/~oleg/ftp/Haskell/number-parameterized-types.html There are a bunch of neat type tricks like this, but the next step up in encoding information in types is dependent type systems like the one used in Epigram: http://www.dur.ac.uk/CARG/epigram/ I recently asked on http://lambda-the-ultimate.org/ what else can be done with type systems other than program safety. I got a neat answer from David Teller: <quote> Static type-checking in Camelot guarantees RAM usage -- not only its safety but also its amount. Static type-checking in my controlled pi-calculus (definitely not a real programming language) guarantees statically properties of access control ("only X can use the printer", "I can only read this information for the purpose of transferring it to you", ...) or resource management ("this program will never require more than x threads, y RAM and z printers"). Static type-checking in TyPiCal guarantees the respect of some protocols. In Acute, you can check the safety of communications... </quote> Type systems can do a lot of neat stuff these days, I've been able to use HaskellDB in my paying work already! -- It seems I've been living two lives. One life is a self-employed web developer In the other life, I'm shapr, functional programmer. | www.ScannedInAvian.com One of these lives has futures (and subcontinuations!)| --Shae Matijs Erisson

feucht＠uni-koblenz.de

3:33 p.m.

On 7 May, Daniel Carrera wrote:

...

Hello,

Right now I'm using type declarations like:

f :: Int -> [Int]

So f returns a list of Ints.

Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size.

Cheers, Daniel.

Hi, you may use a tuple? greetings, Philip

...

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Daniel Carrera

3:33 p.m.

feucht@uni-koblenz.de wrote:

...

you may use a tuple?

Hhhmm... I just tried it. It looks like Hugs doesn't like tuples with more than 5 elements. :-( Oh well. I'll go for array. Cheers, Daniel.

Chung-chieh Shan

5:11 p.m.

Daniel Carrera wrote in article <427D1818.70100@digitaldistribution.com> in gmane.comp.lang.haskell.cafe:

...

feucht@uni-koblenz.de wrote:

...
you may use a tuple? Hhhmm... I just tried it. It looks like Hugs doesn't like tuples with more than 5 elements. :-(

You can nest tuples. And that might be a good idea given that you know the size of the array, and it's conveniently a power of 2. data A2 a = A2 !a !a type A4 a = A2 (A2 a) type A16 a = A4 (A4 a) type A256 a = A16 (A16 a) It's not hard to index or assign into such an "array". You have a choice as to what to use as the type of indices into such an "array". It may be most convenient to use Int, but Word8 prevents out-of-bound errors, and A2 (A4 Bool) would probably be most elegant. (: -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Science operates according to a law of conservation of difficulty. The simplest questions have the hardest answers; to get an easier answer, you need to ask a more complicated question. -- George Musser. Color Madness. Oddball maps can require more than four colors. Sci. Am., January 2003.

Glynn Clements

4:42 p.m.

Daniel Carrera wrote:

...

Right now I'm using type declarations like:

f :: Int -> [Int]

So f returns a list of Ints.

Is there a way to tell Haskell that a list or array must have exactly (say) 256 elements? I'd love to have Haskell make sure that the array I build is the correct size.

For lists, no. For arrays, in the general case, again no. For your specific case, you can use an array whose indices have type Word8 (8 bit unsigned integer), i.e. import Data.Word import Data.Array type ByteMap = Array Word8 Word8 For an RC4 implementation, you should probably be using Word8 throughout rather than Int or Integer. -- Glynn Clements

Daniel Carrera

5:58 p.m.

Glynn Clements wrote:

...

For lists, no. For arrays, in the general case, again no. For your specific case, you can use an array whose indices have type Word8 (8 bit unsigned integer), i.e.

import Data.Word import Data.Array

type ByteMap = Array Word8 Word8

For an RC4 implementation, you should probably be using Word8 throughout rather than Int or Integer.

Thanks for the pointer! Okay, I'll start learning how Arrays and 8-bit words work. That'll keep me busy for a few days. :-) Cheers, Daniel.

7316

Age (days ago)

7319

Last active (days ago)

List overview

Download

50 comments

20 participants

participants (20)

Abraham Egnor
Antti-Juhani Kaijanaho
Benjamin Franksen
Bulat Ziganshin
Chung-chieh Shan
Daniel Carrera
David Roundy
Fergus Henderson
feucht＠uni-koblenz.de
Glynn Clements
Graham Klyne
Hamilton Richards
Jacob Nelson
karczma＠info.unicaen.fr
Marcin 'Qrczak' Kowalczyk
Max Vasin
Sebastian Sylvan
Shae Matijs Erisson
Stefan Monnier
Thomas Davie