In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language?
Well, if you consider large word-processors like word keep a complete undo history, I would keep a document as a list of changes: data Document = Insert Location String | Delete Location Location ... so a document may look like: [Insert 0 "Hello World", Delete 6 10, Insert "\n World"] But you will still need mutable state for the actual edit buffer. You also need to decide if you want to be able to edit files larger than memory... If so a mutable state buffer using the ST monad is probably the way to go (STUArray). Keean. GoldPython wrote:
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
I'm going to take by your replies that you've never worked for a major corporation. :) Thats okay. Cause unless you've really been in the grind of their operations it can seem irrational from the outside I'm giving examples of the difficulties that would be faced in attempting to get managers to agree to the use of the haskell language. You mentioned the fact that there is a school in Europe that teaches this. Now I live in America, which is probably why I'm not familiar with that Institution - I'm sure it's a good one. But I'm not sure how to convey how little impact that that information would have on a discussion I would be having with my management. Most companies when it comes to their internal IT avoid the cutting edge like the plague. They want solid, well proven solutions, not the hot new wave of the future. They also want it in a protocol/language/specification that is well known so that they don't have to pay a premium for the employees. Because the nature of the business world is to pay as little as possible in the hopes of acquiring somone who is just barely competent enough to do the work they require. This may seem jaded, its because I am. I would love to see the better technology win out in the end but that very rarely happens. For me to convince my management to introduce Haskell. I would have to have the following (at a minimum occur) 1) I would be able to point to multiple consulting firms that offer locally available training courses for different skill sets. 2) There would need to be support from the existing engineers/architects who have taken the time on their own behalf to familiarize themselves with the language. 3) Write ups in IT based business articles promoting Haskell. 3) There would need to be known commercial products that fit our needs that's written in Haskell to both demonstrate its usefullness and provide the internal demand for the language. As a side note I googled for consulting firms that trained people in Haskell. I found one - http://www.reid-consulting-uk.ltd.uk based out of the UK. So I'm going to say thats theres probably a better chance of getting Haskell embedded in a british IT dept because of this. But as a comparison. When I googled for the same type of training for Python. I got quite literally hundreds of different firms many of them able to provide training locally to my location. Maybe there is a need for a Haskell Advocacy project. A Website covering why Haskell is a good choice and a central location to obtain information and suggestions on getting Haskell implemented at a business. Jason Keean Schupke wrote:
Jason Bailey wrote:
No offense but those are just catch phrases. They can support a justification but won't work as a justification in its own right.
Here are some questions that I would expect to get from business.
Q:"What have I heard about this technology?" A: Probably nothing. Haskell isn't very well known in the programming community (out of 6 co-workers asked, one had used Haskell in a single college class), let alone the business community. Business has become very wary about accepting technologies that are obscure.
At Imperial College (top european science and technology university) all DOC undergradutes taught Haskell as main teaching language - so no shortage of top-quality trained graduates...
Q:"What can I do with this language that I can't do now?" A:Well nothing. It can certainly do some things better then the current languages out there, but its just another general purpose language.
Get static guarantees that a program won't crash... programs can be buffer-overflow proof (list based strings) and more reliable
Q:"Will it require training?" A: Oh yes, we're talking about a different way of looking at programs. On the surface level it should be fairly easy to pick up but it will take some time before the engineers are able to produce decent work. Oh and there are no training classes we can send people to. They will have to learn on their own.
See answer to 1
Q:"Whats the market like for Haskell programmers?" A: Well there isn't one. Which means that if business was going to advertise for someone with haskell programming knowledge they are going to end some spending a premium on them.
See answer to 1
Q:"Why should we support yet another programming language?" A: Because this is a better language. (Wouldn't work as an answer but I would give it a try. )
Its not yet another programming language - it's the future and you don't want to be left behind...
Keean.
I have the same experience. I wish it wasn't so, but it is.
I've been playing with Haskell since before Haskell 98, and until I
joined this email list a couple weeks ago, I had never met another
human being that knew what functional programming was much less had
done any. I've been working around software for 24 years in four
states in the US, and one country overseas, and I've never even heard
the topic mentioned.
I'm not sure what it says, but there it is.
On Fri, 03 Dec 2004 14:34:43 -0500, Jason Bailey
I'm going to take by your replies that you've never worked for a major corporation. :)
Thats okay. Cause unless you've really been in the grind of their operations it can seem irrational from the outside
I'm giving examples of the difficulties that would be faced in attempting to get managers to agree to the use of the haskell language. You mentioned the fact that there is a school in Europe that teaches this.
Now I live in America, which is probably why I'm not familiar with that Institution - I'm sure it's a good one. But I'm not sure how to convey how little impact that that information would have on a discussion I would be having with my management.
Most companies when it comes to their internal IT avoid the cutting edge like the plague. They want solid, well proven solutions, not the hot new wave of the future. They also want it in a protocol/language/specification that is well known so that they don't have to pay a premium for the employees. Because the nature of the business world is to pay as little as possible in the hopes of acquiring somone who is just barely competent enough to do the work they require.
This may seem jaded, its because I am. I would love to see the better technology win out in the end but that very rarely happens.
For me to convince my management to introduce Haskell. I would have to have the following (at a minimum occur)
1) I would be able to point to multiple consulting firms that offer locally available training courses for different skill sets.
2) There would need to be support from the existing engineers/architects who have taken the time on their own behalf to familiarize themselves with the language.
3) Write ups in IT based business articles promoting Haskell.
3) There would need to be known commercial products that fit our needs that's written in Haskell to both demonstrate its usefullness and provide the internal demand for the language.
As a side note I googled for consulting firms that trained people in Haskell. I found one - http://www.reid-consulting-uk.ltd.uk based out of the UK. So I'm going to say thats theres probably a better chance of getting Haskell embedded in a british IT dept because of this.
But as a comparison. When I googled for the same type of training for Python. I got quite literally hundreds of different firms many of them able to provide training locally to my location.
Maybe there is a need for a Haskell Advocacy project. A Website covering why Haskell is a good choice and a central location to obtain information and suggestions on getting Haskell implemented at a business.
Jason
Keean Schupke wrote:
Jason Bailey wrote:
No offense but those are just catch phrases. They can support a justification but won't work as a justification in its own right.
Here are some questions that I would expect to get from business.
Q:"What have I heard about this technology?" A: Probably nothing. Haskell isn't very well known in the programming community (out of 6 co-workers asked, one had used Haskell in a single college class), let alone the business community. Business has become very wary about accepting technologies that are obscure.
At Imperial College (top european science and technology university) all DOC undergradutes taught Haskell as main teaching language - so no shortage of top-quality trained graduates...
Q:"What can I do with this language that I can't do now?" A:Well nothing. It can certainly do some things better then the current languages out there, but its just another general purpose language.
Get static guarantees that a program won't crash... programs can be buffer-overflow proof (list based strings) and more reliable
Q:"Will it require training?" A: Oh yes, we're talking about a different way of looking at programs. On the surface level it should be fairly easy to pick up but it will take some time before the engineers are able to produce decent work. Oh and there are no training classes we can send people to. They will have to learn on their own.
See answer to 1
Q:"Whats the market like for Haskell programmers?" A: Well there isn't one. Which means that if business was going to advertise for someone with haskell programming knowledge they are going to end some spending a premium on them.
See answer to 1
Q:"Why should we support yet another programming language?" A: Because this is a better language. (Wouldn't work as an answer but I would give it a try. )
Its not yet another programming language - it's the future and you don't want to be left behind...
Keean.
On 2004 December 03 Friday 15:16, GoldPython wrote:
until I joined this email list a couple weeks ago, I had never met another human being that knew what functional programming was
My experience has been different in Massachusetts. At my first job after my Comp Sci degree, developing compilers for a now-defunct minicomputer manufacturer, another developer stated that his favorite programming language was the pure subset of Lisp. These days when I go on site to interview for a job as a C++ programmer, usually at least one of the developers with whom I talk recognizes Haskell on my résumé and knows something of functional programming.
I've never even heard the topic mentioned
Granted, the average programmer can get along on just the information that comes out of the OOP/UML/IDE industry. But the people who brought templates to C++ and generics to Java made no secret of their knowledge of functional programming, and cited these capabilities as they existed in SML and/or Haskell.
Well, if you consider large word-processors like word keep a complete undo history, I would keep a document as a list of changes:
data Document = Insert Location String | Delete Location Location ...
Better to store it as a pair of the most recent state, and a list of *reversed* changes.
--KW 8-)
--
Keith Wansbrough
I imagine you would want to use a truly mutable data structure in the IO monad -- something like an STUArray of Chars. GoldPython wrote:
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
GoldPython
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language?
This is specific to text editors: 1. Use a traditional mutable data structure, e.g. IOArray of IOUArrays (lines), each coupled with "first filled" and "last filled" indices and resized when needed. Implement "undo" by the list of changes. Easy conceptually. Has good performance in common cases and poor performance for unusual data (e.g. very long lines). Easy to make bugs in undo handling. 2. Use a persistent data structure with logarithmic cost of most operations: a balanced tree of text fragments, called a rope (Hans Boehm has made one for C). "Undo" can be made by simply keeping old versions. Hard to implement the core data structure. If done right, the rest is easy, in particular "undo" handling is very robust. There are some overheads for all operations, but the cost of operations scales to extreme cases. The second way is more interesting, but I don't know how to implement a rope in details. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk wrote:
2. Use a persistent data structure with logarithmic cost of most operations: a balanced tree of text fragments, called a rope (Hans Boehm has made one for C). "Undo" can be made by simply keeping old versions.
Hard to implement the core data structure. If done right, the rest is easy, in particular "undo" handling is very robust. There are some overheads for all operations, but the cost of operations scales to extreme cases.
The second way is more interesting, but I don't know how to implement a rope in details.
What happens with this method when the display needs refreshing, does the current state have to be recomputed every time ... wouldn't this lead to very slow cursor operations when using 'backspace'? I would have thought a mutable screen-buffer for editing would still be required. Keean.
Keean Schupke
What happens with this method when the display needs refreshing, does the current state have to be recomputed every time ...
No. The new state is constructed from bits of old state and the changed data. Applying a change on average requires logarithmic time & memory wrt. the whole size. It does not invalidate the old state - state is immutable. http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/sp... -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
G'day all.
Quoting Marcin 'Qrczak' Kowalczyk
2. Use a persistent data structure with logarithmic cost of most operations: a balanced tree of text fragments, called a rope (Hans Boehm has made one for C). "Undo" can be made by simply keeping old versions.
Hard to implement the core data structure. If done right, the rest is easy, in particular "undo" handling is very robust. There are some overheads for all operations, but the cost of operations scales to extreme cases.
The second way is more interesting, but I don't know how to implement a rope in details.
It's quite easy, actually. Leaves of the tree are traditionally arrays of chars (with one big array representing the "original" file), though you could also have something that represents a lazily read file on disk. Internal nodes come in two varieties: - "Restrictions" have one child. A restriction represents a subsequence of the child node. - "Concatenations", which have two children. A concatenation represents two children pasted together. Using only these, you can implement any editing operation. A deletion, for example, is done by restricting the node twice and then pasting the two restrictions together. To keep the tree managable, you need to a) eagerly push restrictions as far down the tree as possible, and b) rebalance. Rather than using a traditional balanced binary tree, it's easier to keep track of the depth of the tree and restructure when it gets too deep. Note that ropes are optimised for _large_ edits. So if you're actually writing a text editor, treating the line currently being edited differently seems worth it. Cheers, Andrew Bromage
GoldPython wrote:
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language?
I wouldn't say that textual data is by its nature mutable. That's just the imperative way of looking at it. The functional way is to think of all possible documents as Platonic entities -- the books in Borges's library -- and of writing a document as the process of choosing which book you want. When you insert or delete a character you're moving your attention from one book to a nearby one. The problem then is finding a way of representing books as values in your program in such a way that "nearby" books, in the above sense, have similar values that can take advantage of sharing. The typical approach is to describe each book inductively as the concatenation of several smaller ones, bottoming out at short phrases (say). Then when you add or delete a character, only one sub-book has changed, and in that sub-book only one sub-sub-book has changed, and so on, so you only need to replace one index at each level, which costs a logarithmic amount of work. -- Ben
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 3 déc. 04, at 17:28, GoldPython wrote:
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language?
Maybe you should take a look at Yi : http://www.cse.unsw.edu.au/~dons/yi.html Cheers, Jérémy. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin) iD8DBQFBsO3d2PUjs9fQ72URAoLLAJ9Dh3Dd6R0r8cqqVs1smifb8MQnPgCfY4cn RB54VIMdsr8CMNwKHb8rgQo= =0TTX -----END PGP SIGNATURE-----
Sweet! I'd love to look it over. Thanks for the link!
On Fri, 3 Dec 2004 23:51:07 +0100, Jérémy Bobbio
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 3 déc. 04, at 17:28, GoldPython wrote:
In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language?
Maybe you should take a look at Yi :
http://www.cse.unsw.edu.au/~dons/yi.html
Cheers, Jérémy. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin)
iD8DBQFBsO3d2PUjs9fQ72URAoLLAJ9Dh3Dd6R0r8cqqVs1smifb8MQnPgCfY4cn RB54VIMdsr8CMNwKHb8rgQo= =0TTX -----END PGP SIGNATURE-----
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (10)
-
ajb＠spamcop.net -
Ben Rudiak-Gould -
GoldPython -
Jason Bailey -
Jérémy Bobbio -
Keean Schupke -
Keith Wansbrough -
Marcin 'Qrczak' Kowalczyk -
Robert Dockins -
Scott Turner