precog

matryoshka

Scala2017–2023

precog / matryoshka

matryoshka

Generalized recursion schemes and traversals for Scala.

Explore on GitHub Read Hacker News discussions

6Distinct people

7Mentions

0Explicit recommenders

823GitHub stars

REPOSITORY AT A GLANCE

What to know before exploring

What it is

Generalized recursion schemes and traversals for Scala.

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 3:56:07 PM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year7 dated mentions

Observed mentions: 2017-08-07 18:33:24 UTC to 2023-01-16 19:51:22 UTC.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges

UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
Period	Start (UTC)	End (exclusive, UTC)	Mentions	Comments
2017	2017-01-01 00:00:00 UTC	2018-01-01 00:00:00 UTC	1	1
2018	2018-01-01 00:00:00 UTC	2019-01-01 00:00:00 UTC	3	3
2019	2019-01-01 00:00:00 UTC	2020-01-01 00:00:00 UTC	1	1
2020	2020-01-01 00:00:00 UTC	2021-01-01 00:00:00 UTC	0	0
2021	2021-01-01 00:00:00 UTC	2022-01-01 00:00:00 UTC	0	0
2022	2022-01-01 00:00:00 UTC	2023-01-01 00:00:00 UTC	0	0
2023	2023-01-01 00:00:00 UTC	2024-01-01 00:00:00 UTC	2	2

What Hacker News says

7 sources

kelseyfrog·Jan 16, 2023

I did work in Scala for a few years. We employed Cats[1], and even a bit of Matryoshka[2] though most of the work I do today is in Python. Nowadays I think about computational requirements in terms of relations among behavioral dependencies. Like, "I want to perform operation O on input A and return a B. To do this, I'll need a way to a -> b and a way to b -> b -> b." I often pass these behavioral dependencies in as arguments and it tends to make the inner core of my programs pretty abstract and built up as layers of specificity. Zooming out nearly all the way, it makes me feel tethered in a qualitatively unique way to certain deep truths of the universe. In a Platonic sense, invoking certain ideas like a monad make me feel like I'm approaching the divine or at least one instantiation of a timeless universal that operates outside of mater

Read the rest

ial existence. I'd imagine some mathematicians might see the universe in a similar way - one where immortal relations between ontological forms exist beyond time and space and at the same time can be threaded through the material world by intellectual observation and when those two meet a beautiful collision occurs. 1. https://typelevel.org/cats/ 2. https://github.com/precog/matryoshka

In Ask HN: How has functional programming influenced your thinking?

consilient·Jan 8, 2023

You can do this with recursion schemes: Haskell: https://hackage.haskell.org/package/recursion-schemes Scala: https://github.com/precog/matryoshka

In Tail Call Optimization: The Musical (2019) [video]

tsuberim·Mar 5, 2019

I got into Haskell a while back and dove deep into the purely functional, strongly typed, category theory rabbit hole. This small but very hard-core community exposed me to completely different (and radical) ideas about programming, software engineering and PL design after I was sure I've seen everything under the sun when it comes to PLs. I soon turned into one of those annoying zealots that keeps preaching functional programming. After a while, I wanted to write my own language/s and set out to build a compiler in Haskell, I kept wanting to make it more and more general brushing against the edges of what the type system could handle and thinking in more and more abstract category theory terms until I just gave up. I felt that the type system was restricting my thinking. Another example of this absurdity in the Haskell way of thinking i

Read the rest

s a very general scala library: https://github.com/slamdata/matryoshka . TL;DR: Haskell makes you think in a deep, general and often very beautiful mathematical way which makes you write beautiful but unintelligible code for the non-mathematician programmer. The switch came when I became increasingly fascinated by machine learning (which is written mostly in Python). Programming in Python felt extremely liberating to me, I could express complex ideas with minimal number of lines that was also obvious for others to read. This is not to say that I abandoned the ideas I learned from the functional land, on the contrary, I still think in a very functional way and Python only made it so much easier to express those concepts. A powerful middle-ground between the two approaches is gradual typing (ie. mypy or typescript) which lets you take advantage of type checker without letting it get in your way, this is the best of both worlds for me. TL;DR: Strong types are for weak (or lazy) minds. Python FTW.

In Ask HN: What made you change your mind about a programming language/paradigm?

aaron-santos·Dec 15, 2018

My experience with recursion schemes was mixed. I applied Matryoshka[1] to a problem involving an algebra of boolean operations on polygons. The implementation was elegant in so far as the essential recursion was lifted out of many separate functions and consolidated. Recursion is always a tricky thing to get right so using recursion schemes avoided an entire class of errors and the implementation was rock solid. The challenge became one of communication. Whereas looping and branching structures are considered fundamental building blocks recursion schemes are not. Team members immediately hit a wall when encountering ana/cata/hylo/*-morphisms. It's like taking a walk through your neighborhood turning a corner and finding an alien artifact. It's also a case of "the math people got there first" ie: the nomenclature hurts rather than helps u

Read the rest

nderstanding. Many times during conversations I wondered how branching and loop control structures were received when introduced decades ago. Were they dismissed or embraced and how much of this was because they were given nice names (if/else/for/while)? In hindsight I'm disappointed that I wasn't exposed to recursion schemes as an undergrad. Recursion schemes are exactly the kind of abstraction found elsewhere in computer science. Also I would also love to see a language with recursion schemes given the same first-class support as the branching and looping constructs we see in almost all languages today. [1] - https://github.com/slamdata/matryoshka

In An Introduction to Recursion Schemes (2014)

azolotko·Dec 13, 2018

You have a pretty narrow definition of a platform. Consider https://en.m.wikipedia.org/wiki/Computing_platform Yes, you are right, I didn't consider the checkcast instruction. Yes, F# does not have this particular limitation, but has few of its own in different places. Most notably, it lacks HKT (arguably, because of CLR awareness of generics). BTW, alternative approaches to stack-safe recursion do exist in Scala. For example, https://github.com/slamdata/matryoshka

In Why Use F#?

lmm·Mar 29, 2018

I could never give up higher-kinded types: there are plenty of ad-hoc solutions to various effects, but a single reusable solution[1] means you can build up libraries that not only handle all the common effects, but your own custom ones as well. Even if you don't use them directly, you benefit from the ecosystem they make possible. Few other languages let you use something like treelog[2], fewer still let you fold a custom tree type while managing an effect as nicely as with matryoshka. Typeclass derivation is reflection done right, with compile-time safety and corresponding performance. I've never seen another language that made it so easy to put a database transaction boundary in exactly the right place but in a type-safe way so that you can never forget, or even have transactions implicitly applied to web endpoints that need them in a

Read the rest

100% statically-compile-time-checked way, because your endpoint routing is just plain old code (the way it is in akka-http[4] or rho[5]). Hell, even when it comes to something as basic as result types: Kotlin or Typescript can't do them (nicely) at all, and Rust's can't offer nice syntax without a macro (or a magic trait in newer versions of the language). There are plenty of things wrong with Scala - in many ways I'd like to see a clean replacement - but now that I think in HKT I could never go back to a language that doesn't have them. [1] http://philipnilsson.github.io/Badness10k/escaping-hell-with... [2] https://github.com/lancewalton/treelog [3] https://github.com/slamdata/matryoshka [4] https://doc.akka.io/docs/akka-http/10.0.4/scala/http/introdu... [5] https://github.com/http4s/rho

In Scala Native 0.3.7

aaron-santos·Aug 7, 2017

Recursion shouldn't be difficult, but we write recursive programs using one tool: self-referential functions. That's like trying to write structured programs using one tool - goto. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire[1] pioneered generalized recursion schemes and influenced work in Haskell[2] and Scala[3]. It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word. [1] - https://maartenfokkinga.github.io/utwente/mmf91m.pdf [2] - https://hackage.haskell.org/package/recursion-schemes [3] - https://github.com/slamdata/matryoshka

In Dijkstra was right – recursion should not be difficult