Been thinking about tail recursion lately. I think compilers should automatically make function definitions like this tail recursive:
fac 0 = 1
fac n | n > 0 = n * fac (n-1)They can do this by noting, each time they recur, that the only thing to do after returning from this recursion is to multiply, or on the second recursion, to multiply twice. On the second recursion, these two multiplications can be simplified into one, right then and there. Like this:
fac 4: (fac 4 = 4 * fac 3) =>
(4*) (fac 3 = 3 * fac 2) =>
(4*) . (3*) (fac 2 = 2 * fac 1) =>
(12*) (fac 2 = 2 * fac 1) =>
(12*) . (2*) (fac 1 = 1 * fac 0) =>
(24*) (fac 1 = 1 * fac 0) =>
(24*) . (1*) (fac 0 = 1) => 24This can compute factorials of arbitrarily large n while using constant stack space. The big deal here is that the compiler has to know when it's able to simplify two composed functions into one; in this case, it has to know that a*(b*c) = (a*b)*c, i.e. * is associative. Comments?
>>51
wot? a pointer is just a number. it doesn't grow or shrink.
>>46
You cannot write foldr with a simple imperative loop because lists in question are one-way and cannot be traversed in the reverse order. Similarly, the problems listed in >>48 cannot be solved efficiently with Haskell, not because Haskell forbids imperative loops, but because lists in Haskell are one-way and immutable.
>>53
And some other data structure can be used instead, right?
Yes, but there are some restrictions, because in Haskell basically all data structures are immutable. When you want to modify an array, you must make a copy of the entire array. You can use mutable arrays, but then you must explicitly sequence their manipulations using monads. There is also a mechanism that presents a immutable interface on top of a mutable array, but the time behavior of resulting arrays is somewhat complicated.
I don't think you understand what is being discussed. Nobody is confused about what tail recursion means. We are discussing where it can be applied, and where not.
So basically my complaint in >>35 is justified - the language does not allow you to implement certain efficient algorithms, due to its inherent limitations?
What if you assume you have functions like "readarray" and "writearray" to do random access to memory arrays? Which points in >>48 could be implemented efficiently then?
>So basically my complaint in >>35 is justified - the language does not allow you to implement certain efficient algorithms, due to its inherent limitations?
No. Using mutable arrays, you can implement any algorithm that can be implemented using imperative languages. Lists are commonly used because they are convinient, but whenever the performance matters, you can use mutable arrays to optimize your program.
>>60
foldr can't be done in O(1) memory and O(n) time in any language, because the lists are singly-linked.
I suppose you could do it with O(1) memory if you didn't mind using O(n^2) time. Evaluate the function on elements n-1 and n, then re-search from the beginning of the list for element n-2, then evaluate the function on n-2 and the previous result, re-search for element n-3, and so on.
If you had a way to specify (or better yet, allow the compiler to infer) that a binary function was commutative and associative, then foldr could be implemented the same way as foldl for such functions. I don't know how much use this would be in practice.
Which is why nobody would use single-linked lists as some sort of generic data type, due to them being far too limited. I guess the problem isn't so much using a functional language as using singly-linked lists in the first place.
oh lawd
>How would that be done in practice, then? I have no idea what "you must explicitly sequence their manipulations using monads" means.
First, two primitive operations on mutable arrays are provided.
readArray :: STArray s i e -> i -> ST e
writeArray :: STArray s i e -> i -> e -> ST ()Here, STArray s i e is something like pointer to array, i is index type of array (usually integer), e is rype of array element, and ST foo is an action whose result is of type foo. For example,
writeArray arr 4 'c'is an action that, when performed, writes 'c' to the 4th element of the array arr.
Next, you can sequencially combine these actions, producing another action. For example,
writeArray arr 4 'c' >> writeArray arr 45 'd'is an action that, when performed, writes 'c' to the 4th element and then writes 'd' to the 5th element of the array arr. Likewise, the following is the function that produce an action that swaps the ith and jth element of a specified array.
swap arr i j =
readArray arr i >>= \x ->
readArray arr j >>= \y ->
writeArray arr i y >>
writeArray arr j xActions that can be combined like the above are called monads.
>>66
Single link list is preferred probably because it's the simplest persistant data structure.
Haskell sucks at lot at arrays. Though there is an interesting module in GHC called PArr, parallel arrays, which is like list comprehensions for arrays.
Well, yeah, I've written quite a number of singly-linked lists too out of laziness because they got the job done, but I wouldn't for a second think to use them as a general data structure. They're just about the most useless data structure out there.
I have nothing constructive to add, but 69 is very similar to tail recursion.
Well, arrays, obviously. Preferrably mutable ones, although I'm sure that would rub somebody's idea of langauge aesthetics the wrong way.
>>64
Nice explanation, thanks.
>>71
See >>64. Haskell is purely functional, so nothing in it can really be mutable. The way you write a real-world program is, roughly, the function "main" evaluates to a sequence of instructions which are then run. That's what monads do; they're basically sequences of instructions, plus a strategy for combining those instructions.
I might not have explained that clearly, though. I just barely understand it all myself.
> Haskell is purely functional, so nothing in it can really be mutable.
Except that >>64 does show how to use mutable arrays, so your statement is pretty silly. They're not first-class language constructs, though, which I think they ought to be, because without mutable arrays, there are large subsets of problems that you can never solve efficiently.
>>73
Not really, though. What >>64 shows is a way to produce instructions, and, when sequenced and eventually bound to "main" in the Main module and executed, those instructions can use mutable arrays (or read input, or produce output, or whatever else they want to do). But evaluating expressions can't have side effects.
Note the return types of readArray and writeArray:
readArray :: STArray s i e -> i -> ST e
writeArray :: STArray s i e -> i -> e -> ST ()Most of the time, you can think of these functions as doing something. But what's really going on is that they are pure functions (no side effects; outputs completely determined by inputs) with return values that are instructions for things to do in the ST monad, as indicated by the "ST e" and "ST ()" in the return types.
In a sense, a Haskell program is an expression that evaluates to an imperative program, which is then run. I hope that makes a little more sense.
But what is that other than semntic games? Your expression has no side effects, but it doesn't give you an answer either. To get your answer, you have to run the generated code with all its side effects.
This is looking more and more like another functional programming eruv to me.
(http://en.wikipedia.org/wiki/Eruv, http://blog.wfmu.org/freeform/2005/06/why_my_hometown.html)
> But what is that other than semntic games?
Quite a lot. All of the functions written in the language are pure, whether in the IO or ST monad or not. Secondly, in practice, the vast majority of code you write is not in these monads. When you have a function with the type "Foo -> Bar", you can be sure it won't surprise you by doing some input.
But what's the value is being "pure" if you don't generate an actual answer?
It seems, to make use of a silly analogy, like a clothing store that proudly claims "We don't harm animals!", and yet sell leather products, and if you try to buy one, you are handed a list that reads "1) Kill a cow..."
I don't think whether the language is pure or not matters so much. Rather, the important thing is what programming style it supports, or what algorithm it can be used to implement. From this point of view, it would be reasonable to say that Haskell has mutable arrays.
Still, I think the default data structure should be persistent one, because it greatly simplifies programming. It may not be lists, though.
From what I understood of the earlier explanation, a function using monads wouldn't return a direct answer, only a program that will compute the answer for you. Yes? No?
>>80
Sorta, yeah, if it's in the IO or ST monad (monads actually do more than that). Yet, most of the functions one will write are not in these monads. As it says in "A Gentle Introduction to Haskell" (http://haskell.org/tutorial/io.html):
> So, in the end, has Haskell simply re-invented the imperative wheel?
> In some sense, yes. The I/O monad constitutes a small imperative sub-language inside Haskell, and thus the I/O component of a program may appear similar to ordinary imperative code. But there is one important difference: There is no special semantics that the user needs to deal with. In particular, equational reasoning in Haskell is not compromised. [...] An experienced functional programmer should be able to minimize the imperative component of the program, only using the I/O monad for a minimal amount of top-level sequencing. The monad cleanly separates the functional and imperative program components. In contrast, imperative languages with functional subsets do not generally have any well-defined barrier between the purely functional and imperative worlds.
> In contrast, imperative languages with functional subsets do not generally have any well-defined barrier between the purely functional and imperative worlds.
I don't see why this would be a positive thing. You've already lost the theoretical advantage of functional languages, no matter how much of "barrier" you put up between imperative and functional code, and for practical code, you'd be much better off with less of a barrier, because in practice, that barrier will just get in the way of actually solving your problem.
>>82
How much practical Haskell programming have you done before arriving at this conclusion?
None. I am merely speaking from general experience with a wide array of programming languages and their quirks and limitations, and the main thing I've learned is that nothing gets in the way of solving a problems efficiently as much as programming language design dogma.
>>84
It depends on what kind of problems you're trying to solve. For quick hacks, Perl is the better tool. For programming large systems, the hardest part is managing complexity, and being able to reason effectively about your program is a huge help. That's where the dogma of purity and referential transparency comes in very, very handy.
Maybe, but for a large projects you will also be solving a lot more different and unrelated problems, and once again programming language flexibility will help you.