Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two Vexing Problems in Functional Programming

matthewbutterick.com

Post reply on HN
Print view View original

101–110 of 217 posts

Re: Two Vexing Problems in Functional Programming

#101

Post by dahfizz »

ChadNauseam wrote: post #39
js8 wrote: post #2

Not sure if the author will read this, but there is a simple answer to both problems. In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. This is somewhat dual to imperat…

> In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write map (\x -> x+1) myli…

> For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying.

This still only works if a child has one / a known-ahead-of-time number of parents. If you need to update an object that N objects point to, you need to update all N references.

Re: Two Vexing Problems in Functional Programming

#102

Post by [deleted] »

TuringTest wrote: post #70
marcosdumay wrote: post #46

Earlier quoted context omitted.

Hum... You declare an state and go modifying it with an action after another. Looks quite imperative to me. The fact that it returns an interpreter instead of values is meaningless if it doesn't change the way you think about the program. If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the lang…

travisathougies is not alone on that. Every one of us functional programmers worth their salt will consider a sequence of transformations from one state to the next as a functional program, as long as there are no side effects outside the current function that may transform state in ways that aren't declared in the types of the input and return values (which would break the referential transparency). Functional React…

[deleted]

Re: Two Vexing Problems in Functional Programming

#103

Post by vnorilo »

ChadNauseam wrote: post #85
vnorilo wrote: post #49

Earlier quoted context omitted.

Not sure there's any benefit in using the state monad for an interpreter. My first thought is to model a cycle of the interpreter as a function of old state into new state. I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data. Now if you have to use a mu…

Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though. When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluat…

Sure, but there are many kinds of interpreters!

I was involved with one that wasn't really demanding in terms of computation, but was distributed in a way that required a lot of speculation and rollbacks. The functional approach was pretty sweet.

Highest speed bytecode interpreter is actually one of the few loops where I prefer assembly to C, as the instruction mix, branch prediction and even the use of stack can be weird from the PoV of a modern optimizing compiler.

Re: Two Vexing Problems in Functional Programming

#104

Post by mirceal »

> To be clear, there’s nothing inher­ently supe­rior about func­tional program­ming. (Despite the fact that these self-contained func­tions are also known as pure func­tions.) It is not the way computers work at a hard­ware level.

Hah. Weird way of approaching it but okay. Here's the thing: it is exactly how computers work at hardware level. If you look at an electronic circuit you and a program written in a functional way, the equivalence is almost 1:1. The circuits are self contained and you compose them to generate a new output from the inputs that are fed in.

Re: Two Vexing Problems in Functional Programming

#105

Post by mirceal »

CornCobs wrote: post #76

I think that copying an entire array just to modify one bit doesn't really demonstrate the flaw of FP as much as it is just bad programming. The problem isn't really with the paradigm, per se, rather it is the understanding of each problem domain. I hate to be pedantic, and I know this sounds like a no true scotsman argument, but I really feel FP discussions always devolve into this because people have so many differ…

strongly agree with you. it should be about the principle and not about a poor understanding and application of the said principle. if the principle is: data should be immutable, data should be immutable. that does not mean copy things over until we throw our hands in the air and say "performance". you also don't mix the semantics of a function call with the underlying representation of the data you are using (if you are using ADT)

Re: Two Vexing Problems in Functional Programming

#106

Post by dahfizz »

TuringTest wrote: post #61
dehrmann wrote: post #44

Earlier quoted context omitted.

> You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. This might be part of the problem with FP. Every popular CPU architecture is imperative.

> Every popular CPU architecture is imperative. That's arguable, given that every (deterministic) imperative computation can be expressed as a pure functional program. "Imperative" is more of a viewpoint that the developer is using to understand the behavior of the computer, rather than a property of the machine itself. A pure functional analysis will describe a computation on that "imperative" architecture as an inm…

You're definitely stretching here. I could just as easily argue that "all of main memory" is the output of any function. Therefore every function is a pure function, and C is a function language. Using your definition, the concept of functional programming is meaningless.

Main memory is state. Registers and cache are state. The entire purpose of the CPU is to mutate state.

Re: Two Vexing Problems in Functional Programming

#107

Post by mirceal »

Barrin92 wrote: post #69

Personally I never really understood the benefit of thinking in functional terms about things that are conceptually more naturally thought of as persistent objects. For example when the author picks "parents" or "children" or in general maybe any entity of any kind, I don't understand what functional thinking gets me. Sure instead of manipulating mutable objects I can think of every entity being 'one thing' at 'one m…

immutability is amazing. you can make assumptions about the data that you have received, it's friendly to caching, it's friendly to crashes, it's very easy to reason about.

it's even more amazing when you enter a territory of multithreading/multi processor.

Re: Two Vexing Problems in Functional Programming

#108

Post by mirceal »

GuB-42 wrote: post #98

Is there a reason for using pure functional programming except as an exercise? Functional programming is great, and most languages nowadays give you the necessary tools like lambdas, closures, list processing, first class functions, etc... but it isn't the right tool for every job. The same languages also typically support object oriented programming with classes, methods, inheritance, encapsulation, etc... Declarati…

yes. there are reasons.

and no, you don't need to go all in. you can make a judgement call and pick and choose what you want to leverage.

for anything but a trivial service immutability of data as you are processing requests should at a minimum be considered.

Re: Two Vexing Problems in Functional Programming

#109

Post by dahfizz »

mirceal wrote: post #104

> To be clear, there’s nothing inher­ently supe­rior about func­tional program­ming. (Despite the fact that these self-contained func­tions are also known as pure func­tions.) It is not the way computers work at a hard­ware level. Hah. Weird way of approaching it but okay. Here's the thing: it is exactly how computers work at hardware level. If you look at an electronic circuit you and a program written in a function…

That works for simple circuits. Actual computers have oodles of state - we usually call it "main memory". Assembly is a language that can only do one thing: mutate this state.

Re: Two Vexing Problems in Functional Programming

#110

Post by lostcolony »

phyrex wrote: post #74
lostcolony wrote: post #56

Earlier quoted context omitted.

Sort of - consider when Lisp originated. The heritage/age comes from a time before the research in persistent data structures happened, or even the issues with mutability were fully known. Because of that, idiomatic Lisp tends to be mutable, and no one is writing a new Lisp who isn't already familiar with another one. That's not to say immutability isn't worthwhile there, or that no Lisp standard libraries support it…

I don’t know about that; clojure was specifically created with persistent data structures in mind, and it’s definitely as much a lisp as racket is

I inserted 'tends' everywhere intentionally.
Post reply on HN