sepp2k

Right

If you want to get rid of the IO-smell altogether, you'd probably go towards functional reactive programming, which is like the purely functional version of event-driven programming.

I suppose the folding function would need to return an option, so it can return None to signal that it's done.

You can get rid of the IO in the callback by making the callback a folding function (i.e. one that takes the result thus-far plus the new value and returns a new result). Then only the final value would be in IO.

Okay, so then in Haskell you'd write an IO function that takes a callback (also in IO), keeps calling peek and sleep until there's a value and then calls the callback with the result of pop.

But then I don't actually know what I'm talking about, so take that with a grain of salt ;-)

But then you're busy-waiting, right? I don't think that's how it actually works.

But at one point there's a primitive, there's got to be.

Or maybe syscall is and putChar calls syscall.

Yes.

I'm no expert on network stuff, but wouldn't polling a socket by registering an interrupt or something like that (which would be done using an OS-specific built-in function, I think)? You could do the same in Haskell (assuming those built-ins exist)

So it's the same in Haskell. putChar is built-in and putStr could be implemented as putStr "" = return () --do nothing when printing an empty string (line break) putStr (c : str) = putChar c >> putStr str

I mean implementing impure functions always means just calling other impure functions unless you're inside the OS, no? Like you couldn't implement putc in C if it weren't built-in. You have a bunch of primitives and the rest of the code calls those primitives.

ST conceptually works in a similar way, but it only allows certain side-effects (specifically mutating mutable data structures) and offers an actual way to get values out of the ST. You can't get at the mutable data structures that way (or at least you can't actually use them), but you can do calculations on mutable data structures inside ST and then use the result from outside of ST. That way your whole program doesn't get tainted when you put the performance-intensive part into ST.

That way IO-functions can't be called from non-IO functions and the side-effects are localized. Fin.

And the main function is then called by the runtime. Because you can't actually call the functions directly from Haskell, this means that the only way an IO-function can be called is by being the main function or by being called by the main-function.

So you take a bunch of impure functions and compose them using monadic operations. And then the final result is an impure function that makes up your main function.

Now return x (which is Haskell's name for the monad operations of type a -> m a) creates an impure function that simply returns x when called. And >>= (i.e. flatmap) is a kind of function composition.

An IO is basically a sequence of side-effecting operations that calculate a value. You can think of it as a function pointer to an impure function (which can never be called directly from Haskell).

How mutability works is that you have magic monads such as IO and ST. They're not implemented as built-ins so they can use mutability as they see fit (so we have the ugly invisible implementations again, but there's no way around that if you want mutability in a pure language).

It's not like that log n makes a difference compared to all the O(1) costs of linked lists. At some point you just have to put your fingers in your ears and sing "lala" when it comes to "small stuff" performance in functional languages ;-)

You usually just use tree-based tables instead

I'm not sure localized mutability would help. At least in Haskell that would mean that all the code that uses the ArrayLists ends up in the IO or ST monad. If the language just allows mutability perioid, it's fine though.

Like in Java and C++ ArrayLists aren't built into the language. Arrays (which are a lot simpler) are and ArrayLists are implemented as classes in the stdlib. If everything is a bunch of built-ins, that feels like smelly language design.

I don't know. When I use a normal ArrayList, like in Java or vectors in C++, I have a good idea of how they're implemented and I can look at their source code or step into it in the debugger whenever I want to. That I couldn't do the same with your functional arraylist because the implementation is hidden behind built-in (assuming a pure language where the impure stuff couldn't be implemented in the language itself), annoys me on a conceptual level.

Plus linked lists are easier to understand (particularly their performance characteristics) and can be implemented with less (and simpler) built-in operations. So that's an important upside from the educational perspective.

From the theoretical point of view, linked list give you the same or better asymptotic performance in all cases. I agree that arrays with internal mutability give you better real-world performance in many real-world use cases, but I suppose functional language designers usually have a more theoretical outlook.

And this could make it very non-obvious when such a copy happens in larger code bases.

What I meant by CoW in this case would be that arr2 causes a copy since it sees that the memory is already shared.

@Alexander Without CoW, I don't see how something like arr1 = original_array + 23; arr2 = original_array + 42; could work correctly. If both arr1 and arr2 try to reuse the memory from original_array, they'll just overwrite each other.

@Alexander You're talking about copy-on-write, right? Otherwise the mutability would be externally visible. Copy-on-write works, but it makes it harder to reason about when appending is O(1) and when it is O(n).

@Alexander Using an immutable array, both would be O(n), so it's not a win and a loss - it's a win and a tie. The advantage is that it's possible to build up an n-element list recursively in O(n) time. Sure it may require using reverse or an accumulator in some cases, but that's still better than not being able to do it all.

Of course a smart compiler could replace the immutable versions of append or modifyArray with mutable versions if it detects that the original array won't be used anymore after the call to append or modifyArray (which is what I meant before with "clever compiler optimizations"). That would many useful cases of building up an array O(n). However that's a non-trivial optimization that makes the language more complex to implement and isn't necessary with linked lists. It also makes it much harder to reason about the performance of programs.

If you know the number of elements, you could also create an n-element array recursively by saying something like f(n) = g(n, createNewArray(n)) and then g(0, arr) = arr; g(n, arr) = { arr2 = modifyArray(arr, n-1, n); g(n-1, arr2) }, where modifyArray(arr, i, x) returns a new array where the ith element of arr is set to x. However that will still have quadratic runtime because modifyArray would be an O(n) operation.

@Kos How would you build up an array of n elements recursively without mutating it in O(n) time? Even if you know n before hand? Any operation that took an array arr of n-1 elements and an element x and would return an array of n elements, containing the elements of arr as well as x without changing the value of arr would have to take O(n) time. If you leave out the "without changing the value of arr" part, it's possible in (ammortized) O(1) time of course, but then we're no longer talking about immutable data structures.

@Izkata The OP uses the term "array" exactly three times. Once to say that FP languages use linked lists where other languages use arrays. Once to say that arrays are better at partial sharing than linked lists and once to say that arrays can be pattern matched just as well (as linked lists). In all cases he's contrasting arrays and linked lists (to make the point that arrays would be more useful as a primary data structure than linked lists, leading to his question why linked lists are preferred in FP), so I don't see how he could be using the terms interchangeably.

@Izkata The OP was talking about partially sharing arrays though, not lists. Also I've never heard what you're describing referred to as partial sharing. That's just sharing.

@DeadMG Yes, but not to immutable arrays.

@gallais That's not the same thing though. In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is.

I'm going to sleep now. Good night everybody.

Where x = f(n)

The thing was, I was just trying to come up with something, such that once I have the number $x$, the best algorithm for the problem is obviously in $\Theta(x)$

@RanG Edited. Does that address your question?

Do you mean because outputting a number is an O(log n) operation and not O(1)? Because that hasn't occurred to me until just now. Let me change my proof-attempt.

Sure, if you tell me which part you're having trouble with.

Well, technically I don't require anything because I just asked out of curiosity. But what I wanted to know is Theta. I already understand that it's true for Omega.

@Raphael Yapp, thanks.

Hm, that doesn't necessarily mean the answer to my question is "yes" though, does it? I mean it's not quite the same, right? For one thing I don't restrict myself to "time-constructable" functions.

Thanks.

I don't know. I'm not an expert. As I said, I was afraid it would be something well-known.