Hot answers tagged

56

I'm not sure about universal definitions of purity, but from the point of view of Haskell (a language where programmers tend to care about things such as purity and referential transparency), only the first of your functions is "pure". The second version of add isn't pure. So in answer to your question, I'd call it "impure" ;) According to this definition, ...


16

There is no fundamental difference. The function map has O(n) complexity, because it iterates over a list of size n and applies an operation to each element. The loop which is explicit in your first example just happens inside the map function. A typical implementation of map could be: map f [] = [] map f (x:xs) = f x : map f xs Here it is easy to see ...


7

Big O notation is absolutely relevant for any program which will be executed on physical hardware. As an example, Clojure is a functional programming language, and its own documentation lists the Big O notation for operations on its data structures (particularly the collections - list, vector, and map). Knowing the Big O factors for each collection will ...


7

So I think that we need to eliminate the term "shared state" from your question, because shared state is almost diametrically opposed to the notion of using immutability to avoid locking. In your example, you basically said that both read some value "N" and both create a new object with a value "N+1". The key is that you wouldn't necessarily save the value ...


6

If you don't care about the side effect, then it's referentially transparent. Of course it's possible that you don't care but someone else does, so the applicability of the term is context-dependent. I don't know of a general term for precisely the properties you describe, but an important subset are those that are idempotent. In computer science, slightly ...


3

I don't know how such functions is called (or whether there even is some systematic name), but I would call function that is not pure (as other answers cowered) but always returns same result if supplied with same parameters "function of its parameters" (compared to function of its parameters and some other state). I'd call it just function, but ...


3

What happens when two threads are trying to generate a new shared state? Let's be clear about what I understand your question to be: You have some mutable variable of immutable state. Let's use an int for simplicity: int x = 42; Then you want two threads to both try to increment x by 1. Then you get to synchronize them. Immutability provides little ...


3

From the compiler's point of view, there's very little difference between a closed over variable and a function argument. They are just given to the function's symbol table at different times. In general you would prefer the closure version, because it is simpler, but if it were a longer function, or shared by other functions, you might want to pull it out ...


3

It's more of a design exercise than a general recommendation. You aren't usually going to put a queue between all your direct function calls. That would be ridiculous. However, if you don't design your functions as if a queue might be inserted between any of the direct function calls, you cannot justifiably claim you have written reusable and composable ...


2

Afaic, at least in C#, at least sometimes behind the scenes a class is generated to store captured variables in it's fields. It is a significant overhead compared to stack allocation to pass parameter directly. As of C#, Raymond Chen has excellent explanation of closures: When faced with this “hard” type of anonymous method, wherein variables are shared ...


2

What about in a functional language? map (*2) prev How is the complexity calculated for this? Obviously, each call to a subroutine adds another instruction, but there are no "steps" to measure. There are steps we can measure! In Haskell, map can be defined like this: map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (a:as) = f a : map ...


2

First of all: this has nothing to do with "Big O". Big O has nothing to do with complexity, algorithms, programming, computer science, etc. Big O simply compares growth rates of functions. It doesn't care what the functions describe, or whether they even describe anything at all. What you are asking about, is simply figuring out the cost (runtime cost, ...


2

It basically depends on whether or not you care about the impurity. If the semantics of this table are that you don't care how many entries there are, then it's pure. Else, it's not pure. Or to put it another way, it's fine as long as optimizations based on purity don't break program semantics. A more realistic example would be if you were trying to debug ...


2

The problem that you have is that you're looking at simplified example, which is so far simplified that you've entirely removed the immutable state from it and left only a single (albeit atomic) mutable value. That's not a realistic example of an immutable system. To bring some immutability back into it, consider a different example. Two threads are ...


2

Aren't locks only needed if you're changing state? There is a subtlety here. Locks are needed not only if the current thread wants to modify the state, but if any any other thread might modify the state. This means that you can only safely elide the object if you know that no other part of the system will modify it. In other words, you can only elide ...


1

What do you call a function [for which] the same input will always return the same output, but also has side effects? Such a function is called deterministic An algorithm whose behavior can be completely predicted from the input. termwiki.com Regarding state: Depending on whose definition of a function you use a function has no ...


1

The answer is pretty easy, with immutability, you don't change state rather you create new state(s). So you have 2 processes both getting input from the same state. What you end up with is 3 things: first the original state, and 2 new states which is the output from the 2 processes. What you need now is a third process dedicated to putting those states ...



Only top voted, non community-wiki answers of a minimum length are eligible