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

Functional programming jargon in plain English

github.com

Post reply on HN
Print view View original

181–190 of 191 posts

Re: Functional programming jargon in plain English

#181

Post by cratermoon »

hither_shores wrote: post #176
b3morales wrote: post #139

Earlier quoted context omitted.

I agree, and not just the English. There is use of particular notation that does not explain anything unless you already know what it means: > f is a morphism from a -> b, and g is a morphism from b -> c; g(f(x)) must be equivalent to (g • f)(x) If I don't already understand (g • f)(x) this is not helpful at all. This other one especially jumped out at me (perhaps because I've personally never seen this "bent equals…

> What does that sign ≍ mean? Normally, `f ≍ g` means `f \in \Theta(g)`. Here, the author is using it as an equals sign. I have no idea why.

Except it's not and =, it's a ≍ sign, which looks almost identical. I'm not a mathematician and I don't know the deep theory behind functional programming, but the internet tells me that ≍ in Graham, Knuth, and Patashnik's Concrete Mathematics it's defined to mean the same thing as "Big Θ"[1], as you note.

1 https://math.stackexchange.com/questions/764897/what-does-th...

Re: Functional programming jargon in plain English

#182

Post by imbnwa »

chongli wrote: post #70
nine_k wrote: post #67

It looks like the Partial Application section is missing the most widespread form of partial application, known as "creating an instance". class A: def foo(self, x): # do something a = A() foo(1) # self is already "applied".

That's a very good point. People think of functional programming languages and OOP languages as entirely separate worlds that, like oil and water, do not mix. In reality they're equivalent, they just have different ergonomics. For example, lambdas can be translated to anonymous inner classes.

>For example, lambdas can be translated to anonymous inner classes.

That's how Java 8 more or less implements them, no?

Re: Functional programming jargon in plain English

#183

Post by GnarfGnarf »

olodus wrote: post #76
GnarfGnarf wrote: post #75

Can someone clarify something for me? If you build a linked list or a dynamically growing array in a Functional program, am I correct in understanding that the array is never modified, instead a copy is made and the new element is added to the copy of the array?

The result should be that after the addition you should not have affected the old array yes. The most basic way of implementing this is what you described. However, there are a number of different ways to optimize this. Since you know that the elements are immutable, if you add the new element to the start of the list you could just point it to the old elements and you now have two lists which share the majority of t…

So... what happens when my array grows to 2GB, and I have millions of copies because I added millions of entries?

Re: Functional programming jargon in plain English

#184

Post by dllthomas »

shikoba wrote: post #165
dllthomas wrote: post #161

Earlier quoted context omitted.

There is a reason in principle that you can't build a Set Monad that works that way: it violates the functor laws. In order to be a functor, you need `fmap (f . g) == fmap f . fmap g`. The problem is that some functions (for instance, Data.Set.showTree) can produce different results for two values that compare equal. For instance, imagine we have a set containing (only) the lists `[1,2]` and `[2,1]`; let's call it s.…

İ prefer to say that show tree violates the abstraction. You can have s1=s2 but not f(s1)=f(S2). So f (show tree) is not a real function (or = is not a real equal). But showtree is a debug function, it doesn't count. İt's like saying in C that a=13 and b=13 isn't a real equality because &a and &b are not equal. There is the underlying structure and the structure after the equivalence. You have to know of what you're…

I'm not unsympathetic to that position, but I think it's ill advised to take it as far as "Functor means functor up to Eq". I grant that showTree in particular is a debug function that will usually be called at the end of any meaningful computation, and handwaving it in particular away is probably fine. I don't think we can say the same of something like splitRoot, which instead breaks the abstraction for the sake of efficiency.

> You have to know of what you're talking.

And the language (/ecosystem) gives you no way of specifying, so we have to be somewhat conservative. I've actually been thinking (partly driven by trains of thought such as under discussion here) that it might be very interesting to have a language that let you reason explicitly about different sorts of equality (tentatively defined, in the context of the language, as indistinguishability relative to some interface).

Re: Functional programming jargon in plain English

#185

Post by Jtsummers »

GnarfGnarf wrote: post #183
olodus wrote: post #76

Earlier quoted context omitted.

The result should be that after the addition you should not have affected the old array yes. The most basic way of implementing this is what you described. However, there are a number of different ways to optimize this. Since you know that the elements are immutable, if you add the new element to the start of the list you could just point it to the old elements and you now have two lists which share the majority of t…

So... what happens when my array grows to 2GB, and I have millions of copies because I added millions of entries?

1. You switch to a pragmatic language that gives you an escape hatch to mutate data.

2. You use a persistent data structure that lets it grow without needing to make millions of copies for millions of new entries.

3. You use a different constructor pattern to avoid the allocations.

For (3), a common way around this (with lists) would be to build it in reverse and then reverse it (assuming that the order actually mattered at all, if it doesn't you don't need to reverse it at the end). This is done in Erlang, for instance, as a common pattern:

  make_something_n_times(0, Acc) -> reverse(acc);
  make_something_n_times(N, Acc) -> make_something_n_times(N-1, [f(N) | Acc]).
You end up with two copies of the list, one in the constructed order and the reverse ordered version, but the constructed order one will be garbage collected in short order. Two copies, better than millions of copies.

You also see a pragmatic solution in Erlang with iolists. These are lists that contain items that you'd want to send to, well, IO functions. But instead of forcing you to allocate whole new strings for concatenation (a common thing to do with strings) like this:

  S1 ++ S2 %% results in allocating a new string and copying contents from at least S1
You can do this:

  Concatenated = [S1,S2]
Now it's a two-element list that references the two prior ones, you've allocated some new memory, but just enough for a new list. Now you have a third string you want to prepend?

  [S3,Concatenated]
Again, minimal amount of allocation and copying (there is no copying). You can use this pattern in other situations and only flatten when needed, or "flatten" it by recursing over the structure to access all the elements but never actually constructing a flattened version.

Re: Functional programming jargon in plain English

#187

Post by GnarfGnarf »

Jtsummers wrote: post #185
GnarfGnarf wrote: post #183

Earlier quoted context omitted.

So... what happens when my array grows to 2GB, and I have millions of copies because I added millions of entries?

1. You switch to a pragmatic language that gives you an escape hatch to mutate data. 2. You use a persistent data structure that lets it grow without needing to make millions of copies for millions of new entries. 3. You use a different constructor pattern to avoid the allocations. For (3), a common way around this (with lists) would be to build it in reverse and then reverse it (assuming that the order actually matt…

OK, thanks for the detailed answers. I am trying hard to learn what I can about FP. I've only been doing this programming thing since 1965.

Is there an FP equivalent of the C++ STL (Standard Template Library)?

Re: Functional programming jargon in plain English

#188

Post by shikoba »

dllthomas wrote: post #184
shikoba wrote: post #165

Earlier quoted context omitted.

İ prefer to say that show tree violates the abstraction. You can have s1=s2 but not f(s1)=f(S2). So f (show tree) is not a real function (or = is not a real equal). But showtree is a debug function, it doesn't count. İt's like saying in C that a=13 and b=13 isn't a real equality because &a and &b are not equal. There is the underlying structure and the structure after the equivalence. You have to know of what you're…

I'm not unsympathetic to that position, but I think it's ill advised to take it as far as "Functor means functor up to Eq". I grant that showTree in particular is a debug function that will usually be called at the end of any meaningful computation, and handwaving it in particular away is probably fine. I don't think we can say the same of something like splitRoot, which instead breaks the abstraction for the sake of…

It's called math.

Re: Functional programming jargon in plain English

#189

Post by Jtsummers »

GnarfGnarf wrote: post #187
Jtsummers wrote: post #185

Earlier quoted context omitted.

1. You switch to a pragmatic language that gives you an escape hatch to mutate data. 2. You use a persistent data structure that lets it grow without needing to make millions of copies for millions of new entries. 3. You use a different constructor pattern to avoid the allocations. For (3), a common way around this (with lists) would be to build it in reverse and then reverse it (assuming that the order actually matt…

OK, thanks for the detailed answers. I am trying hard to learn what I can about FP. I've only been doing this programming thing since 1965. Is there an FP equivalent of the C++ STL (Standard Template Library)?

So when you ask about the STL I can interpret that in several ways:

1. Good sized standard library for many common tasks, yes. You won't have to reinvent the wheel using functional programming languages. Though the size and scope of their standard libraries will vary. And when it's not in their standard library, code reuse is a thing and most have decent to good package managers for obtaining what amounts to community-standard solutions to problems not covered by the language standard.

2. Generic data structures. Definitely yes. Either by virtue of being dynamically typed (Erlang, the Lisp family) or because parametric polymorphism (roughly analogous to C++'s generics) has been a standard thing for 4 or 5 decades for the statically typed ones (ML family, Haskell).

3. Generic algorithms. See (2).

Re: Functional programming jargon in plain English

#190

Post by eddyschai »

mypalmike wrote: post #133
eddyschai wrote: post #128

Earlier quoted context omitted.

Maybe if I explain what a Monad is in Plain English it'll help you understand functors? A monad is just a monoid in the category of endofunctors.

I think you need to explain endofunctors. An endofunctor is the category containing monoids such as the monad.* *This is probably wrong. Please don't explain.

So in all seriousness a functor is a mapping from one category to another, and an endofunctor is a mapping from one category to the same category.
Post reply on HN