On Thu, Mar 07, 2002, Michael Ruth wrote:

Hello,

I am pretty new to Functional programming, and I am having the following problem.

I need to sort a list of dates provided in an input file. One date per line.. day month year is the order. And each is represented by integers seperated by spaces. And once the list is sorted output the results to a file.

I having trouble knowing where to start. This is what I was thinking the best line of attack was:

This actually sounds pretty reasonable (though I don't know whether quicksort is best or not... maybe someone else can say). To save programming, you may want to use the lazy IO primitives, but I don't particularly suggest it. There is a function called map (defined in the standard prelude) that you will probably find useful for one of these steps. Why don't you write this up and send it to the list so that we can look at code rather than English text?

--read in the lines one by one into a list

--then iterate thru the list while breaking the strings into [Int] list -- of 3 elements [day,month,year]

--then quicksort overall list

--then print out overall list line by line

I understand this is a imperative approach, but this is the way I was taught how to program, well that and OOP. How do I go about writing this in a functional sense ? And is there another way to do this AKA another plan of attack ?. Thanks very much for your time and consideration.

Michael

_________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.

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

On Fri, Mar 08, 2002, Ketil Z. Malde wrote:

I don't think it's either functional nor imperative by itself. The question is how you structure it, do you say something like

buffer x list y

x = readFile ... y = parse x quickSort y print y

(which would be imperative), or do you say something like

print (quickSort (parse (readFile ...)))

Unfortunately, this is wrong. You'd have to do something more like readFile ... >>= print . sort . parse

which would be functional. Note that the only really imperative part is the sorting, which actually changes the content of y for the following part of the program. A functional implementation wouldn't destroy y, but create a new list with the elements from y in sorted order.

yah.

I'm not sure if that made things clearer :-)

(If you really want to implement it, look at the Prelude for some help, some of the things you wish to do is pretty standard fare. And sorting is perhaps made easier if you rearrange the list of dates a bit?)

Sorting is probably easiest if you use the standard sort function. I'm still kind of interested in whether anyone has done work on which purely-functional sorts are efficient, and particularly which ones are efficient in GHC. David Feuer

Sorting is probably easiest if you use the standard sort function. I'm still kind of interested in whether anyone has done work on which purely-functional sorts are efficient, and particularly which ones are efficient in GHC.

I think it was Oege de Moor who compared a number of sorting algorithms in Haskell. It turned out that the quicksort we all know and love is very slow: it is much better to use merge sort. Maybe Oege remembers more details? John Hughes