Skip to content

Instantly share code, notes, and snippets.

P. Oscar Boykin johnynek

Block or report user

Report or block johnynek

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@johnynek
johnynek / Dagify.scala
Created Nov 8, 2019
An algorithm to build a DAG out of any directed graph.
View Dagify.scala
package com.stripe.unprotonated
import scala.collection.immutable.SortedSet
object Graph {
/**
* Build a DAG by merging individual nodes of type A into merged nodes of type SortedSet[A]
*/
final class Dagify[A: Ordering](seed: Set[A], val neighbors: A => Set[A]) {
@johnynek
johnynek / almosttailrec.scala
Last active Nov 8, 2019
A generalization of tail recursion for stack safety in scala
View almosttailrec.scala
/*
* Consider a simple recursive function like:
* f(x) = if (x > 1) f(x - 1) + x
* else 0
*
* This function isn't tail recursive (it could be, but let's set that aside for a moment).
* How can we mechanically, which is to say without thinking about it, convert this into a stack safe recursion?
* An approach is to model everything that happens after the recursion as a continuation, and build up that
* continuation in a stack safe manner. Here is some example code:
*/
@johnynek
johnynek / RefMap.scala
Last active Oct 14, 2019
A wrapper on ConcurrentHashMap to use with cats.effect.Ref
View RefMap.scala
package org.bykn.refmap
import cats.data.State
import cats.effect.Sync
import cats.effect.concurrent.Ref
import java.util.concurrent.ConcurrentHashMap
import cats.implicits._
/**
@johnynek
johnynek / dotty_list.scala
Last active Sep 11, 2019
Implementation of linked list using dotty features (opaque type, union types, extension methods, type lambda).
View dotty_list.scala
// unfortunately
// opaque type Fix[F[_]] = F[Fix[F]]
// won't work (no recursion in opaque type), but this implementation is safe, but scary due to asInstanceOf
object FixImpl {
type Fix[F[_]]
inline def fix[F[_]](f: F[Fix[F]]): Fix[F] = f.asInstanceOf[Fix[F]]
inline def unfix[F[_]](f: Fix[F]): F[Fix[F]] = f.asInstanceOf[F[Fix[F]]]
}
@johnynek
johnynek / map_module.scala
Last active Mar 13, 2019
A module based encoding of Map which keeps the ordering associated with the Map. Then we can talk about `mymod.Map` as a type, knowing that `mymod.ordering` is the ordering.
View map_module.scala
abstract class MapModule {
type K
def ordering: Ordering[K]
type Map[_]
def empty[V]: Map[V]
def updated[V](m: Map[V], key: K, v: V): Map[V]
def get[V](m: Map[V], key: K): Option[V]
def items[V](m: Map[V]): Stream[(K, V)]
def remove[V](m: Map[V], key: K): Map[V]
View Array covariance unsoundness.java
class B { }
class Main {
public static void main(String[] args) {
B strMain = Main.<String>cast("this is not a b");
System.out.println(strMain.toString());
}
public static <A extends Object> B cast(A a) {
B[] ary = new B[1];
@johnynek
johnynek / y.py
Last active Mar 3, 2019
Here is a port of this example y-combinator code: https://rosettacode.org/wiki/Y_combinator#Python except manually rewriting the lambdas into top-level functions accessing dictionaries to create closures.
View y.py
def make_lambda(captured, fn, arity):
return {
"cap": captured,
"fn": fn,
"arity": arity,
"applied": [],
}
def apply_lambda(lam, arg):
app0 = lam["applied"]
View buildcart.scala
package org.bykn.buildcart
import cats.{Alternative, Applicative, Id, Eq, Monad, Order, Traverse}
import cats.data.{Chain, Const, State}
import scala.collection.immutable.SortedSet
import cats.implicits._
object BuildCart {
trait Hash[A]
@johnynek
johnynek / TreeList.scala
Created Dec 14, 2018
Implementation of "Purely Functional Random Access Lists" by Chris Okasaki in scala. This gives O(1) cons and uncons, and 2 log_2 N lookup.
View TreeList.scala
package org.bykn.list
import cats.Applicative
import cats.implicits._
/**
* Implementation of "Purely Functional Random Access Lists" by Chris Okasaki.
* This gives O(1) cons and uncons, and 2 log_2 N lookup.
*/
@johnynek
johnynek / defer_stack_overflow
Created Oct 30, 2018
Hit a stack overflow in Eval.defer in cats 1.4.0
View defer_stack_overflow
[info] at cats.Eval$.loop$1(Eval.scala:367)
[info] at cats.Eval$.cats$Eval$$evaluate(Eval.scala:372)
[info] at cats.Eval$Defer.value(Eval.scala:258)
[info] at cats.Eval$.loop$1(Eval.scala:351)
[info] at cats.Eval$.cats$Eval$$evaluate(Eval.scala:372)
[info] at cats.Eval$Defer.value(Eval.scala:258)
[info] at cats.Eval$.loop$1(Eval.scala:351)
[info] at cats.Eval$.cats$Eval$$evaluate(Eval.scala:372)
[info] at cats.Eval$Defer.value(Eval.scala:258)
[info] at cats.Eval$.loop$1(Eval.scala:351)
You can’t perform that action at this time.