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

Functors, Applicatives, and Monads

thecoder.cafe

Post reply on HN
Print view View original

71–80 of 90 posts

Re: Functors, Applicatives, and Monads

#71

Post by codebje »

alabastervlog wrote: post #25
burlesona wrote: post #13

I feel like Haskell is easier to use than it is to explain, and in my experience a lot of these kind of tutorial / explanations actually make things seem harder and more complicated than just working with the concepts and observing what they do. (This one included.)

Every “hard” concepts I’ve seen in Haskell is immediately clear to me if explained in almost any other language. The hard part is Haskell, not the concept. Usually I’m left wondering why whatever-it-is even has a name, it’s so simple and obvious and also not that special or useful seeming, it’d never have occurred to me to name it. I guess the people giving them names are coming at them from a very different perspect…

Haskell has a type system that lets these things be directly useful in ways they cannot be in many other languages.

You can't, in Java, declare anything like "class Foo extends Functor>", or use a similar generic annotation on a method: you can't have an unapplied type-level function as an argument to another type-level function.

These things get a name in Haskell because they can be directly used as useful abstractions in their own right. And perhaps because Haskell remains very close to PL research.

Re: Functors, Applicatives, and Monads

#72

Post by pests »

globnomulous wrote: post #18
burlesona wrote: post #13

I feel like Haskell is easier to use than it is to explain, and in my experience a lot of these kind of tutorial / explanations actually make things seem harder and more complicated than just working with the concepts and observing what they do. (This one included.)

I'm not familiar with Haskell and am really, really struggling to follow the article. In the case of the functor, the author doesn't explain in technical, specific enough terms the difference between "open the box, extract the value out of it, apply the function, and put the result back in a box" and "apply a function to a box directly; no need to perform all the steps ourselves." I have no idea what 'apply a functio…

To try to answer your first question, coming form someone who is also not an expert in Haskell or monads.

"apply a function to a box directly; no need to perform all the steps ourselves."

The box doesn't change, and it also doesn't matter what's inside of it. You are attaching the function to the box, who later knows how to apply it to itself. If you were to open the box, you would need to know how to handle all the possible contents. It's key here that you are only handling a box and nothing else.

Re: Functors, Applicatives, and Monads

#73

Post by robto »

rebeccaskinner wrote: post #20
edflsafoiewq wrote: post #10

Earlier quoted context omitted.

A list [b] is a container for bs indexed by integers. A function a->b is a container for bs indexed by as.

> A function a->b is a container for bs Anecdotally, this is one of those things that's trivially true to some people, but really hard for other people to internalize. I think it's why the "container" can lead people astray- if you haven't internalized the idea of functions as being indexed by their argument, it's a really mind twisting thing to try to make that leap.

One of the fun things about Clojure that reinforces this "trivially true" perspective is that maps and sets are functions:

    ;; "maps" the keys to the values
    (map {1 "a" 2 "b"} (take 5 (cycle 1 2))) ;;=> '("a" "b" "a" "b" "a")
    ;; acts as a predicate that tests for membership
    (filter #{"a" "b" "c"} ["a" "b" "c" "d" "e" "f"]) ;;=> '("a" "b" "c")
Once you get used to this idiom you naturally start thing of other functions (or applicative functors) the same way. The syntax sugar makes for some very concise and expressive code too.

Re: Functors, Applicatives, and Monads

#74

Post by rebeccaskinner »

magicalhippo wrote: post #67
rebeccaskinner wrote: post #52

Earlier quoted context omitted.

I've recently started writing a series of blog posts ( https://rebeccaskinner.net/posts/2024-10-18-dictionaries-are... ) trying to explain the idea and my approach has been to explain the idea using comprehensions. I haven't had a lot of people review the post yet, and I still have at least one if not two more follow-ups before it's done, so I'm not yet sure how well the idea will land.

Nice introduction. Still not entirely sold that dictionaries are pure functions, though. Will you be covering common dictionary operations like adding/removing elements and iterating over the dictionary keys? I have some ideas on how one might frame it in a pure function setting but they all seem quite contorted in a similar way to your incrementDict, ie you'd never actually do that, so curious if there are better wa…

I'm really focusing less on the idea that Dict the data type with it's associated methods is like a function, and more on the idea that a dictionary in the general sense is a mapping of input values to output values, and you can think of functions that way.

That said, there are some pretty reasonable analogies to be made between common dictionary operations and functions.

For example, adding and removing items can be done with function composition so long as you are okay with partial lookups. Here's a really short example I put together:

  module Example where
  import Control.Applicative

  type Dict a b = Eq a => a -> Maybe b

  emptyDict :: Dict a b
  emptyDict = const Nothing

  singleton :: a -> b -> Dict a b
  singleton k v target
    | k == target = Just v
    | otherwise = Nothing

  unionDict :: Dict a b -> Dict a b -> Dict a b
  unionDict dict1 dict2 k = dict1 k  dict2 k

  insertDict :: a -> b -> Dict a b -> Dict a b
  insertDict k v dict = singleton k v `unionDict` dict

  removeDict :: a -> Dict a b -> Dict a b
  removeDict k dict target
    | k == target = Nothing
    | otherwise = dict k
This particular representation of dictionaries isn't necessarily something you'd really want to do, but the general approach can be quite useful when you start working with something like GADTs and you end up with things like:

  data Smaller a where
    SmallerInt :: Smaller Int
    SmallerBool :: Smaller Bool
  
  data Larger a where
    LargerInt :: Larger Int
    LargerBool :: Larger Bool
    LargerString :: Larger String
  
  someLarger :: Larger x -> x
  someLarger l =
    case l of
      LargerInt -> 5
      LargerBool -> True
      LargerString -> "foo"
  
  embedLarger ::
    (forall x. Larger x -> Smaller x) ->
    (forall smallerI. Smaller smallerI -> r) ->
    (forall largerI. Larger largerI) -> r
  embedLarger mapping fromSmaller larger = fromSmaller (mapping larger)
(I'm actually co-authoring a talk for zurihac this year on this pattern, so I have quite a bit more to say on it, but probably not ideal to cram all of that into this comment).

Re: Functors, Applicatives, and Monads

#75

Post by nsonha »

snickell wrote: post #65
rthnbgrredf wrote: post #2

This reminds me of https://www.adit.io/posts/2013-04-17-functors,_applicatives,... I think over the recent years, there's been a rise in typed languages that support functional programming like TypeScript and Rust. It will be interesting to see if this trend continues in the context of AI assistant programming. My guess is that it will become easier for beginners, and the type systems will help to build more robust p…

Even in early 2025, LLMs are already the most powerful type inference algorithm. Why would they need a static type system in 2030? My guess is it'll be the opposite: I suspect compared to humans, LLMs will make fewer type errors, and more errors that are uncaught by types. Thus I expect type systems will be of lower value to them (compared to humans), leading to a shift toward dynamic languages and the possible extin…

> Why would they need a static type system in 2030?

Why do many people talk about type systems as if they're only a safety guard?

To me that's never the main role of type systems. I don't know what's the word for it, but types allow me to read the code, on a high level. Sure AI will write them but as long as software engineers exist, we still have to read the code. How do you even read code without types? Comments? Unit tests? Actual implementation?

> LLMs will make fewer type errors, and more errors that are uncaught by types

> extinction of typed languages

Don't you find these contradictory? If LLM increases the rate of error uncaught by types, then type systems or the usage of them should catch up, otherwise there is no magical way for software to get better with LLM.

In the current state of LLM, the type system (or lsp and/or automated tests) is what allows the "agentic" AI coder to have a feedback loop and iterate a few times before it hands off to the programmer, perhaps that gives the delusion that the LLM is doing it completely without type system.

Re: Functors, Applicatives, and Monads

#76

Post by magicalhippo »

rebeccaskinner wrote: post #74
magicalhippo wrote: post #67

Earlier quoted context omitted.

Nice introduction. Still not entirely sold that dictionaries are pure functions, though. Will you be covering common dictionary operations like adding/removing elements and iterating over the dictionary keys? I have some ideas on how one might frame it in a pure function setting but they all seem quite contorted in a similar way to your incrementDict, ie you'd never actually do that, so curious if there are better wa…

I'm really focusing less on the idea that Dict the data type with it's associated methods is like a function, and more on the idea that a dictionary in the general sense is a mapping of input values to output values, and you can think of functions that way. That said, there are some pretty reasonable analogies to be made between common dictionary operations and functions. For example, adding and removing items can be…

> and more on the idea that a dictionary in the general sense is a mapping of input values to output values, and you can think of functions that way.

So what's the difference between a map and a dictionary then?

> Here's a really short example I put together

Much appreciated. I don't really know Haskell (nor any other functional language), but I'm pretty sure I understood it.

> This particular representation of dictionaries isn't necessarily something you'd really want to do

Yeah that's pretty much what I had in mind, and yes it's possible but it feels forced. For one you're not actually removing an element, you just make it impossible to retrieve. A distinction that might seem moot until you try to use it, depending on the compiler magic available.

> I'm actually co-authoring a talk for zurihac this year on this pattern

Sounds interesting, will check it out when it's published.

Re: Functors, Applicatives, and Monads

#77

Post by snickell »

nsonha wrote: post #75
snickell wrote: post #65

Earlier quoted context omitted.

Even in early 2025, LLMs are already the most powerful type inference algorithm. Why would they need a static type system in 2030? My guess is it'll be the opposite: I suspect compared to humans, LLMs will make fewer type errors, and more errors that are uncaught by types. Thus I expect type systems will be of lower value to them (compared to humans), leading to a shift toward dynamic languages and the possible extin…

> Why would they need a static type system in 2030? Why do many people talk about type systems as if they're only a safety guard? To me that's never the main role of type systems. I don't know what's the word for it, but types allow me to read the code, on a high level. Sure AI will write them but as long as software engineers exist, we still have to read the code. How do you even read code without types? Comments? U…

> How do you even read code without types?

We're not going to settle the preference for dynamic vs static types here. Its probably older than both of us, with many fine programmers on both sides of the fence. I'll leave it at this: well-informed programmers choosing to write in dynamically typed languages DO read code without types, and have happily done so since the late 1950s (lisp).

The funny thing is, I experience the same "how do you even??" feeling reading statically typed code. There's so much... noise on the screen, how can you even follow what's going on with the code? I guess people are just different?

> LLMs will make fewer type errors, and more errors that are uncaught by types

The errors I'm talking about are like "this CSS causes the element to draw part of its content off-screen, when it probably shouldn't". In theory, some sufficiently advanced type system could catch that (and not catch elements off screen that you want off-screen)? But realistically: pretty challenging for a static type system to catch.

The errors I see are NOT errors that throw exceptions at runtime either, in other words, they are beyond the scope of current type systems, either dynamic (runtime) or static (compile time). Remember that dynamic languages ARE usually typed, they are just type checked at runtime not compile time.

> perhaps that gives the delusion that the LLM is doing it completely without type system.

I mentioned coding in JS with cline, so no delusion. It does fine w/o a type system, and it rarely generates runtime errors. I fix those like I do with runtime errors generated when /I/ program with a dynamic language: I see them, I fix them. I find they're a lot rarer in both LLM generated code and in human generated code that proponents of static typing seem to think?

Re: Functors, Applicatives, and Monads

#78

Post by bobbylarrybobby »

globnomulous wrote: post #18
burlesona wrote: post #13

I feel like Haskell is easier to use than it is to explain, and in my experience a lot of these kind of tutorial / explanations actually make things seem harder and more complicated than just working with the concepts and observing what they do. (This one included.)

I'm not familiar with Haskell and am really, really struggling to follow the article. In the case of the functor, the author doesn't explain in technical, specific enough terms the difference between "open the box, extract the value out of it, apply the function, and put the result back in a box" and "apply a function to a box directly; no need to perform all the steps ourselves." I have no idea what 'apply a functio…

The distinction is that in general “opening a box and extracting the value” makes no sense, as it's not a thing that can be done in general. If your box is a Maybe, there might not be a value to extract. If it's a list, there might be zero or multiple values. It only ever makes sense to map over the contents of the box, replacing the values with their image under the map.

Re: Functors, Applicatives, and Monads

#79

Post by IshKebab »

yodsanklai wrote: post #55
IshKebab wrote: post #19

The problem with Monads etc. is that they're simple concepts with extremely confusing names. Monad should be FlatMappable. Once it has the correct name it barely even needs an explanation at all.

FlatMappable doesn't capture what a monad is. For instance, you can do async programming using monads. Doesn't relate to FlatMappable. I think you don't see the need for a new name if you don't grasp the concept. It's like in mathematics, you have tons of algebraic structures, like monoid, groups, fields, rings. They all represent categories of things which share some properties. You don't want to name the category b…

I don't know, I think the fact that you can use FlatMappables to do async programming and pure IO etc. doesn't mean you have to capture all of the potential uses in the name.

I mean... you can use timer interrupts to do preemptive multi-threading but we don't feel the need to give them a confusing name.

Re: Functors, Applicatives, and Monads

#80

Post by Tainnor »

snickell wrote: post #65
rthnbgrredf wrote: post #2

This reminds me of https://www.adit.io/posts/2013-04-17-functors,_applicatives,... I think over the recent years, there's been a rise in typed languages that support functional programming like TypeScript and Rust. It will be interesting to see if this trend continues in the context of AI assistant programming. My guess is that it will become easier for beginners, and the type systems will help to build more robust p…

Even in early 2025, LLMs are already the most powerful type inference algorithm. Why would they need a static type system in 2030? My guess is it'll be the opposite: I suspect compared to humans, LLMs will make fewer type errors, and more errors that are uncaught by types. Thus I expect type systems will be of lower value to them (compared to humans), leading to a shift toward dynamic languages and the possible extin…

A well-typed program provides a soundness proof that can be straightforwardly verified by just compiling the program. Even in a humongous codebase in a slow-to-compile language, this is cheaper than e.g. running an LLM on your codebase every time you push a commit (especially if you use incremental compilation). Type systems, even simpler ones, just give a lot of bang for the buck.
Post reply on HN