Functional-Imperative Hybrid

Question

Pure functional programming languages ​​do not allow volatile data, but some calculations are more naturally / intuitively expressed in imperative order - or an imperative version of the algorithm may be more efficient. I know that most functional languages ​​are not clean and allow you to assign / reassign variables and do imperative things, but generally prevent this.

My question is: why not allow the local state in local variables, but require that the functions can only access their local and global constants (or just constants defined in the outer scope)? Thus, all functions support referential transparency (they always give the same return value, taking into account the same arguments), but inside the function, the calculation can be expressed in imperative terms (for example, in a while loop).

IO, and this can be achieved in the usual functional ways - through monads or passing through the token "world" or "universe."

Answer 1

Short answer: there are systems that allow what you want. For example, you can do this using the ST monad in Haskell (as noted in the comments).

ST monad approach from Haskell Control.Monad.ST . Code written in the ST monad can use links ( STRef ) where convenient. The nice part is that you can even use the results of the ST monad in clean code, since it is essentially autonomous (this is basically what you wanted in the question).

The proof of this autonomous property is through a type system. The ST monad contains a state-stream parameter, usually denoted by a variable of type s . When you have such a calculation, you will have a monodic result with a type of type:

 foo :: ST s Int 

To turn this into a net result, you should use

 runST :: (forall s . ST sa) -> a 

You can read this type, for example: give me a calculation, where a parameter of type s does not matter, and I can return the result of the calculation without ST baggage. This basically keeps the mutable ST variables from escaping, since they will carry s with them, which will depend on the type system.

This can be used for a good effect for clean structures that are implemented with basic mutable structures (for example, a vector package ). You can undo immutability for a limited time to do something that mutates the underlying array. For example, you could combine an immutable Vector with a package of impure algorithms to maximize the performance characteristics of in-place sorting algorithms and still get clean.

In this case, it will look something like this:

 pureSort :: Ord a => Vector a -> Vector a pureSort vector = runST $ do mutableVector <- thaw vector sort mutableVector freeze mutableVector 

The thaw and freeze functions are linear-time copying, but this will not violate the O (n lg n) total runtime. You can even use unsafeFreeze to avoid another linear traversal, since the mutable vector is no longer used.

Answer 2

My question is why local state cannot be allowed in local variables, but require that functions can only access their own locales and global constants (or just constants defined in the outer scope)?

Good question. I think the answer is that volatile locals have limited practical value, but volatile data structures distributed in heaps (mostly arrays) are extremely valuable and form the basis of many important collections, including efficient stacks, queues, sets, and dictionaries. Thus, limiting the mutation for local residents would not otherwise give the purely functional language any important advantages of the mutation.

In the corresponding note, the transfer of sequential processes exchanging purely functional data structures provides many advantages of both worlds, since sequential processes can use mutations within the country, for example, variable message queues - 10 times faster than any purely functional queues. For example, this is idiomatic in F #, where the code in MailboxProcessor uses mutable data structures, but the messages sent between them are immutable.

Sorting is a good study in this context. Sedgewick quicksort in C is short and simple and hundreds of times faster than the fastest purely functional view in any language. The reason is that quicksort mutates the array in place. Mutated locals won't help. Same story for most graph algorithms.