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

15-150: Principles of Functional Programming

brandonspark.github.io

Post reply on HN
Print view View original

81–90 of 146 posts

Re: 15-150: Principles of Functional Programming

#81

Post by philsnow »

kccqzy wrote: post #74
imslavko wrote: post #35

Slightly off-topic but what's a good forum to seek help on FP practices outside of the courses like this online? Every winter break I get back into trying to learn more FP (in Haskell) and in the past several years I have been practicing algo problems (codeforces, advent of code, leetcode). I always get stuck on more advanced graph algorithms where you traverse a and modify a graph, not a tree structure - it gets par…

Many graph algorithms are designed for imperative programming. It's safe to say that functional graph programming is still in its infancy. Alga[0], a system for algebraic graphs only came out in 2017. And efficient algorithms for graphs may yet to be discovered (even something as simple as reversing a list that's both efficient and elegant only came out in 1986!) That said, as a beginner in functional programming, it…

I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could:

> [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style.

[0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf

[1] https://en.wikipedia.org/wiki/Purely_functional_data_structu...

Re: 15-150: Principles of Functional Programming

#82

Post by convolvatron »

medo-bear wrote: post #58
albedoa wrote: post #40

Earlier quoted context omitted.

For those of us who are unfamiliar with Lisps, can you expand on how they break referential transparency (and how Standard ML contrasts in that regard)?

He is probably talking about namespaces. In common lisp, for example, (a a) calls a function 'a' on a variable 'a'. Lisp knows this because the first thing that comes after the left paren is a function

more importantly there are functions (using scheme as an example) like set! and set-cdr! that mutate existing values and totally break referential transparency.

this isn't just user facing - for example let* kind of depends on creating bindings up front so they work across clauses, and then mutating them afterwards

Re: 15-150: Principles of Functional Programming

#83

Post by squillion »

ElectricalUnion wrote: post #53
frozenlettuce wrote: post #31

My complaint with FP: Sometimes I just want to do something silly, like adding a log somewhere. If I choose to add said side effect, now all my functions are marked with an io signature (so there might be _other_, nastier side effects hiding there as well - mainly an issue if you have multiple people contributing to the same project). If I don't add the side effect, and choose to refactor multiple layers of code, I w…

From my limited knowledge of FP languages it is expected that pure code in fact doesn't evaluate anything until a monad forces it to evaluate. You would then need a monad to evaluate the things you're attempting to log. And at that point you have a monad, so you can log as usual?

It's not about monads, it's about effectful code, which is represented by special types (e.g. IO in Haskell, Eff in PureScript). Effectful code can call pure code, but not vice-versa. Since a program will have to do something, the main function is always effectful, i.e. it returns an effectful special type. So you're right that pure code isn't evaluated until some effectful code is ultimately returned by the main function and executed (by a runtime or equivalent). However, in purely functional languages most code is pure, even though it's ultimately called by effectful code.

Monads and side-effects aren't intrinsically related. Simplifying, a monad is something with flatMap() - in JavaScript, Array and Promise are monads (kinda). What flatMap() gives you is the ability to chain things, which is useful to sequence side-effects so that they can be performed by a machine in a given order. That's why IO and Eff are monads.

Re: 15-150: Principles of Functional Programming

#84

Post by _a_a_a_ »

brandonspark wrote: post #26
frankbreetz wrote: post #8

Does this include exercises? I didn't see any and I always find that the most useful part of learning.

Unfortunately, it does not. These lectures are "mine", in the sense that I developed all of them myself, but the homeworks and lab exercises are the combined efforts of generations of TAs and instructors from the past. It wouldn't be right for me to give them away. (they are also reused from time to time, so there are academic integrity concerns with that also)

[flagged]

Re: 15-150: Principles of Functional Programming

#85

Post by gtchuang »

shortrounddev2 wrote: post #49
medstrom wrote: post #39

Earlier quoted context omitted.

If you expect perfect factual accuracy from your teachers, yeah. On the flip side, they don't have the curse of knowledge yet i.e. it's still fresh in their mind what was difficult in the beginning, so they can probably explain very well. Just keep in mind who's teaching you, and it's just like if a co-student teaches you. And if you feel you have to take what you hear with a grain of salt, that's probably good for y…

I just mean in terms of experience. If you deviate from textbook accuracy and go into providing practical advice for real-life scenarios, someone with only a bachelor's and no work history is someone who can only give you canned anecdotes from others. Looking at his resume, it looks like he's had some internships so he has a bit of experience, and that's probably worth something

His main day job is as a SWE doing program analysis, so I'm pretty sure he's got the credentials to talk about real-life scenarios.

Re: 15-150: Principles of Functional Programming

#86

Post by poorlyknit »

frozenlettuce wrote: post #31

My complaint with FP: Sometimes I just want to do something silly, like adding a log somewhere. If I choose to add said side effect, now all my functions are marked with an io signature (so there might be _other_, nastier side effects hiding there as well - mainly an issue if you have multiple people contributing to the same project). If I don't add the side effect, and choose to refactor multiple layers of code, I w…

In Haskell you have a lot of options to type your functions in a more granular way. Consider the type class MonadIO, which lets you specify that your function works on any monad that can do side effects, not just IO specifically:

    -- Before
    captureAudioDuration :: DeviceID -> DiffTime -> IO WaveData
    -- After
    captureAudioDuration' :: MonadIO m => DeviceID -> DiffTime -> m WaveData
You can build the same thing, but for logging!

    class Monad m => MonadLog m where
        log :: String -> m ()
    -- In IO, just log to stdout.
    -- Other implementations might be a state/writer monad
    -- or a library/application-specific monad for business logic.
    instance MonadLog IO where
        log msg = putStrLn ("log: " ++ msg)
    -- Before: Bad, doesn't actually do any IO but logging
    findShortestPath :: Node -> Node -> Graph -> IO [Node]
    -- After: Better, type signature gives us more details on what's happening.
    -- We can still use this in an IO context because IO has a MonadLog instance.
    -- However, trying to capture audio in this function using either
    -- of the functions above will lead to a type error.
    findShortestPath' :: MonadLog m => Node -> Node -> Graph -> m [Node]
As you can imagine this can get quite verbose and there's other patterns one can use. Feel free to ask any follow-up questions :)

Re: 15-150: Principles of Functional Programming

#87

Post by weatherlight »

SomeRndName11 wrote: post #78
weatherlight wrote: post #73

Earlier quoted context omitted.

because SML is awesome, isn't going to change and is simple. you can learn the syntax in an afternoon, and really focus on learning FP semantics.

The problem that is extremely verbose though. OCaml is much more concise.

Both languages encourage a concise, functional programming style but with different flavors and toolsets. They are comparable, in terms of verbosity.

I think these are correct implementations of the tower of Hanoi.

OCaml

    let rec hanoi n source target auxiliary =
      if n > 0 then begin
        hanoi (n - 1) source auxiliary target;
        Printf.printf "Move disk from %s to %s\n" source target;
        hanoi (n - 1) auxiliary target source
      end
SML

    fun hanoi n source target auxiliary =
      if n > 0 then (
        hanoi (n - 1) source auxiliary target;
        print ("Move disk from " ^ source ^ " to " ^ target ^ "\n");
        hanoi (n - 1) auxiliary target source
      )
function definition, if expressions, recursion are more concise in SML, string interpolation is nicer in OCaml

Re: 15-150: Principles of Functional Programming

#88

Post by shortrounddev2 »

gtchuang wrote: post #85
shortrounddev2 wrote: post #49

Earlier quoted context omitted.

I just mean in terms of experience. If you deviate from textbook accuracy and go into providing practical advice for real-life scenarios, someone with only a bachelor's and no work history is someone who can only give you canned anecdotes from others. Looking at his resume, it looks like he's had some internships so he has a bit of experience, and that's probably worth something

His main day job is as a SWE doing program analysis, so I'm pretty sure he's got the credentials to talk about real-life scenarios.

Yeah idk anything about the guy

Re: 15-150: Principles of Functional Programming

#89

Post by chriswarbo »

agomez314 wrote: post #11

Great resource! Forgive my ignorance but why do so many modern functional programming courses use Standard ML instead of a Lisp dialect? Is it because of its built-in type-checking, or is it just how it's always been taught?

"Lisp" is pretty broad. Whilst it was inspired by Lambda Calculus (the core of most FP languages), a lot of Lisp code is quite imperative (loops, mutable variables, control flow separate from data flow (e.g. exceptions/errors), etc.).

Scheme (and its dialects/descendants) tend to stick to a more functional style (although they also like to do stack-gymnastics with continuations, etc.). Many courses are based around Lisp.

One of the main features of the ML family is static typing, with algebraic datatypes, pattern-matching, etc. (i.e. the stuff that new languages like to call "modern", because they first saw it in Swift or something). That gives a useful mathematical perspective on code ("denotational semantics", i.e. giving meaning to what's written; as opposed to the common "operational semantics" of what it made my laptop do), and having type checking and inference makes it easier to do generic and higher-order programming (dynamic languages make that trivial in-the-small, but can make large systems painful to implement/debug/maintain/understand). This course seems to take such abstraction seriously, since it covers modules and functors too (which are another big feature of the ML family).

NOTE: In ML, the words "functor" and "applicative functor" tend to mean something very different (generic, interface-based programming) to their use in similar languages like Haskell (mapping functions over data, and sequencing actions together)

Post reply on HN