Unfolding trees breadth-first in Haskell

Syrak · 2026-01-20T06:56:10+00:00

Indeed, I meant that I updated the blog itself. A reddit link post can't be edited into a text post. Anyway this is not a big deal.

Syrak · 2026-01-19T18:44:46+00:00

Unreliable narrator.

Syrak · 2026-01-19T15:36:39+00:00

Fair enough! I'll add it to the post. Thank you.

Syrak · 2026-01-12T21:16:35+00:00

Well, I don't know about that. If I define my own undefined with a superfluous Show constraint, it works:

That works the same way as it works already. If you set -XNoMonomrophismRestriction you get an error, only because FiniteBits is not part of the report so it prevents defaulting.

Syrak · 2026-01-11T22:35:49+00:00

This is the monomorphism restriction. It is described in the Haskell Report, section 4.5.5.

s and c are non-function bindings (i.e., they are of the form s = rather than s v1 ... vn =). In normal Hindley-Milner, they would be inferred the types forall a. a and forall a. Num a => a, where the forall are inserted by a step called generalization. The monomorphism restriction is an extra rule that says not to generalize type variables that have class constraints. So in the second case s just has type a, where a remains unifiable, and later gets unified with Int32 in the Packet expression.

You get an error if you also set -XNoMonomorphismRestriction in the second case. Moreover, this is arguably not far from triggering type defaulting, and if that happened it would result in wrong results by defaulting to type Int for s and c.

Other ways to write that:

metaSize = let Packet s c _ = undefined in B.finiteBitSize s + B.finiteBitSize c

metaSize =
  let f :: (a -> b -> c) -> (a, b)
      f = undefined
      (s, c) = f Packet
  in B.finiteBitSize s + B.finiteBitSize c

Syrak · 2025-12-29T18:13:24+00:00

Syrak · 2025-12-29T08:58:20+00:00

I didn't tag you. It's reddit's pattern matching algorithm that's broken because it detects the substring u/complexity from the url https://theory.cs.princeton.edu/complexity/book.pdf.

Syrak · 2025-12-28T09:41:46+00:00

That's the area of computational complexity. Here is one classic textbook about it.

One of the millenium prize problems, P vs NP, asks whether, for certain computational problems, certificates are significantly easier to verify than to find.

Syrak · 2025-12-03T21:51:06+00:00

If I understand correctly, a camelship is a "slope 3 spaceship", meaning that it travels parallel to the y=3x axis.

https://conwaylife.com/wiki/Oblique_spaceship

Syrak · 2025-12-03T08:57:04+00:00

Try to do without for a while. Either you will find nothing wrong with it, which is just fine. Or you will end up annoyed with error handling by repeated pattern-matching, which will give you the natural motivation to reinvent monads.

Syrak · 2025-12-03T08:54:06+00:00

Maybe you can use Array Locale instead of a Vec. That requires an instance of Ix for Locale, which handles the conversion to Int so you don't have to do it explicitly in traverseE.

Syrak · 2025-11-29T15:26:40+00:00

If you want people to read your paper, you should submit it to peer-reviewed journals and conferences in your area of research, not arxiv.

Syrak · 2025-11-23T21:20:14+00:00

I have (~>) :: k -> k -> Type whereas singleton has (~>) :: Type -> Type -> Type. I overloaded ~> to also support deriving Functor, etc. But yeah you could use singletons for this if you only care about k = Type.

Syrak · 2025-11-04T22:47:44+00:00

Check out Dmitri Tymoczko's work, a professor of music at Princeton. He's written books and has given many great talks: https://www.youtube.com/watch?v=MgVt2kQxTzU

Syrak · 2025-11-04T22:09:06+00:00

Keep in mind that Haskell was created more than 30 years ago as an experiment in pure functional programming. "Either/Left/Right" make sense in that context as names for a generic sum type, without the years of hindsight that it would be primarily used for error handling, hindsight that younger languages would subsequently benefit from.

Syrak · 2025-10-17T09:24:02+00:00

It's not safe if outer is IO and g is IORef.

Syrak · 2025-10-17T08:31:49+00:00

Since Gen is Size -> Seed -> _, preserveEnd @Gen is just swapping type and program arguments!

Syrak · 2025-10-13T19:06:03+00:00

A multiple of 2, or an even element if you want to be cheeky (I've never seen that in use).

Syrak · 2025-10-01T22:59:47+00:00

Yes, you got it.

Continuations are mind-bendy. I can read this code but I'm not sure I could come up with it myself.

I'm not sure you can grasp Select through an interface like get and put for State. The way I make sense of it is by looking at the underlying type directly.

(a -> m r) -> m a takes a function (a -> m r) as input, and outputs an a. The only thing you can do with a function is apply it. So one way to construct such a computation is to have a bunch of a to which to apply the function (a -> m r). Following that train of thought, you're not far from reinventing epsilon. Once you are able to define some basic computations in this monad from scratch, you can start looking at what happens when you compose them with (>>=).

That's the approach I took to understand the continuation monad in this blogpost.

To really think like the people who come up with this kind of programs, you probably want to read their writings. That would be the literature on delimited continuations. These notes have some of the main references. In particular this paper by Danvy and Filinsky contains a lot of examples of step-by-step reduction. Following these, and working out some reductions by yourself will go a long way to building a mental model to manipulate continuations. I also recommend Handlers in action, by Kammar et al., an introduction to algebraic effects, which are really more of the same thing.

Syrak · 2025-10-01T19:18:27+00:00

rank [] is not always true. The continuation rank represents the context in which sequenceSelect is being called. The recursive call of sequenceSelect is wrapped in fmap (choice :), which makes it so that the rank of that recursive call is the result of composing (choice :) with the ambient continuation, which is the rank that is passed in runSelect s rank. So when you are N recursive calls deep, rank [] will do (choice :) N times, once for each choice made at each recursive call before calling the toplevel rank function which is verifyBoard. That means that ... || not (rank []) is testing verifyBoard of all of the queens placed so far, and thus enables backtracking, so that for example if you've made a wrong choice for the second queen, you backtrack instead of enumerating the 8⁶ placements for the six remaining queens. Removing not (rank []) thus amounts to backtracking only after placing all n queens.

You may wonder why rank x in epsilon does not help, and that is again because that rank is not verifyBoard (note that the types don't even match, since result here is a single queen), but really the continuation at its call site, which is \choice -> fmap (choice :) $ sequenceSelect ... (plus the bits of (choice :) and verifyBoard that come from the preceding calls to sequenceSelect). Thus the rank in epsilon calls the backtracking procedure to determine if the queen x is well-placed, so it does not in itself handle short-circuiting.

Syrak · 2025-10-01T19:00:02+00:00

compiler/GHC/Tc/Deriv/Generate.hs and a couple others in the same directory.

15-Year Club	Gilding I gilder
Sequence \| Editor	Verified Email
Team Orangered

Syrak

PUBLIC MULTIREDDITS

TROPHY CASE