anfelor

Joined 5 years ago

Karma

339

Submissions

Member since

Jun 30

meet.hn/city/55.9533456,-3.1883749/City-of-Edinburgh

Socials: - github.com/anfelor - antonlorenzen.de ---

View on Hacker News

Recent submissions

Comment · 2 years ago

Yes, that is true! Koka's constructor contexts also allow you to do this. A constructor context is a data structure with exactly one hole which you can fill in with an arbitrary value (or even several arbitrary values, copying the constructor context in the process).

Comment · 2 years ago

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398)

Comment · 2 years ago

Disclosure: I work on Koka's FBIP optimization (Option 4).

> The most efficient data structure to use here would be a mutable dynamic array and in an imperative language that's what pretty much everyone would use. But if you asked an OCaml programmer, they would almost certainly use a linked list instead.

I agree with this sentiment. However, OCaml does have mutable arrays that are both efficient and convenient to use. Why would a programmer prefer a list over them? In my opinion, the main benefit of lists in this context is that they allow pattern matching and inductive reasoning. To make functional programming languages more suited for array programming, we would thus need something like View Patterns for arrays.

> Unfortunately, this makes it impossible to use any standard functions like map on linear values and either makes linearity nearly useless or inevitably creates a parallel, incomplete universe of functions that also work on linear values.

You can implement polymorphism over linearity: this is done in Frank Pfenning's SNAX language and planned for the uniqueness types in a branch of OCaml.

> This might sound a little dangerous since accidentally holding on to a reference could turn a linear time algorithm quadratic

No, the in-place reuse optimization does not affect the asymptotic time complexity. But it can indeed change the performance drastically if a value is no longer shared since copies are needed then.

> A tracing garbage collector just doesn't give you this sort of information.

It is possible to add One-bit Reference Counts to a garbage collector, see https://gitlab.haskell.org/ghc/ghc/-/issues/23943

> for now even these struggle to keep up with tracing garbage collectors even when factoring in automatic reuse analysis.

I investigated the linked benchmarks for a while. The gap between Koka and Haskell is smaller than described in that initial comment, but a tuned GHC is indeed a bit faster than Koka on that benchmark.

Comment · 2 years ago

Perhaps contrary to most people in this thread, I think you should avoid learning lenses or category theory too early. These are great tools, but they take months or even years to master and are not required to write useful code in the language.

I find Haskell very useful for my projects, but to achieve this I restrict myself to the basic subset of the language (Haskell 2010, no fancy extensions such as type families or GADTs) and use few libraries aside from the core libraries. New features and libraries always carry a high learning curve in Haskell and less popular libraries can be buggy. Instead, you will often be more productive just writing the required functionality from scratch (and it will teach you more too!).

At Jane Street, I saw my coworkers learn functional programming in just one week. (some still struggled with monads in the second week -- if that is you, I can recommend Phil's paper: https://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/b...). If you are learning Haskell in your free time and with no one experienced to help, it will obviously take you longer. If you have questions, feel free to post on the Haskell IRC or Reddit. Just don't worry that you need to read another tutorial before getting started :)

Comment · 2 years ago

Another interesting data structure related to skiplists but not mentioned here are zip trees: https://arxiv.org/abs/1806.06726

The are a tree-based version of skiplists and thus more suited to functional programming / immutable datastructures.

Comment · 2 years ago

You can use more external displays using a dock and DisplayLink Manager though. I got three extra monitors to run on my M1 Air with no problems that way.

Comment · 2 years ago

Some of the research behind Koka was discussed at:

FP2: Fully In-Place Functional Programming [pdf] - https://news.ycombinator.com/item?id=36471591 - July 2023 (24 comments)

Perceus: Garbage Free Reference Counting with Reuse [pdf] - https://news.ycombinator.com/item?id=25464354 - Dec 2020 (44 comments)

Implementing Algebraic Effects in C - https://news.ycombinator.com/item?id=14887341 - July 2017 (21 comments)

Comment · 3 years ago

The headline "GPT-4 increased BCG consultants’ performance by over 40%" is misleading since it implies that they became more productive in their actual work, when this is a carefully controlled study that separates tasks by an "AI frontier". Only inside the frontier did the "quality" of work increase by 40%, while they completed 12% more tasks on average.

Comment · 3 years ago

Sure, it would be great to chat! If you are interested in contributing to Koka at some point, there might also be opportunities there :)

Comment · 3 years ago

These are two different languages, see https://effekt-lang.org/ and https://koka-lang.github.io/koka/doc/index.html -- although I believe that the FP^2 work mentioned by OP currently only works in Koka (and perhaps soon in Lean; https://leanprover.github.io/)

Comment · 3 years ago

Thanks, I am surprised and delighted to see our paper here! We also wrote a follow-up recently, which you may enjoy: https://www.microsoft.com/en-us/research/uploads/prod/2023/0...

Comment · 3 years ago

I would also recommend Koen Claessen's simplified finger trees (https://dl.acm.org/doi/abs/10.1145/3406088.3409026) and Zip trees (https://arxiv.org/pdf/1806.06726.pdf) for purely functional skip lists.

Comment · 3 years ago

On the contrary, I think this is a great example for how similar co-working spaces look. Even though this company apparently tried hard to make them look different, the pictures are so similar:

- All the ceilings have exposed "industrial" elements such as ventilation pipes, cables or unpainted metal.

- They are all very spacious with lots of exposed floor but no carpets (to make them easier to clean I assume)

- Modern, minimalist furniture

- The occasional plant here and there, but potted as to not introduce any dirt

- Non-distracting and almost bland color scheme. Notice how even the painting on the wall fades into the background.

How could this look different? Consider for example NeueHouse or Soho House from https://www.architecturaldigest.com/story/top-coworking-spac...

They have more vibrant colors, more contrasts, less open space and more furniture overall. There are bookshelves and many unneeded but beautiful items like vases or small paintings. The ceilings have exposed wood and the floors are covered by carpets or are at least patterned.

Comment · 3 years ago

Intuition from category theory has certainly been useful for some programming language features (eg. algebraic effects, modal types or lenses), but I don't think it has helped with the things you cite. Rusts ownership model was created with little formal, academic understanding - or do you mean more foundational stuff like linear logic? And I don't think that Haskell does supercompilation today? It does optimize a whole lot but that is more due to laziness and other optimizations. But neither these optimizations nor supercompilation have much to do with category theory as far as I am aware.

Comment · 3 years ago

Ah thanks! I didn't find that paper, is it online somewhere?

You may also be interested in the stack allocation system in OCaml: https://www.youtube.com/watch?v=yGRn5ZIbEW8 In particular, Stephen gives a nice example in the end how it can avoid some allocations of lambdas (but it also would need to box the closure in the CPS-reverse).