DEV Community: Molossus Spondee

Free monoidal functors in arbitrary categories

Molossus Spondee — Mon, 05 Oct 2020 04:58:22 +0000

It is often joked "a monad is a monoid in the category of endofunctors."

Little known fact, an Applicative functor is a monoid in the category of functors with day convolution as the product.

And day convolution unlike endofunctor composition can be defined over any strong monoidal category (basically just has tuples and functions.)

Hence

{-# LANGUAGE ExistentialQuantification, RankNTypes #-}
import Prelude hiding (Functor (..), Applicative (..))
class Functor f where
  fmap :: Hom a b -> f a -> f b
class Functor f => Monoidal f where
  pure :: Id a -> f a
  join :: Day f f a -> f a
data Day f g a = forall x y. Day (f x) (g y) (Hom (PRODUCT x y) a)
instance Functor (Day f g) where
   fmap f (Day h x y) = Day (f :.: h) x y
data Id a = Id (forall x. Hom x a)
instance Functor Id where
    fmap f (Id x) = Id (f :.: x)
data Free f a = Pure (Id a) | Ap (Day f (Free f) a)
instance Functor (Free f) where
   fmap f (Pure x) = Pure (fmap f x)
   fmap f (Ap x) = Ap (fmap f x)
instance Monoidal (Free f) where
   pure = Pure
   join (Day h (Pure x) y) = Ap h x y

Where PRODUCTand Hom are up to you to define.

In order to have full applicative functors you need functions which your category might not have.

Codata/Data with Type Classes and Tagless Final Style

Molossus Spondee — Tue, 28 Jul 2020 16:10:37 +0000

Lately I have been playing with tagless final style, a way of writing data structures in Haskell which is supposedly more extensible. I don't really see it as all that advantageous myself.

A trivial linked list example.

class List t where
    nil :: t
    cons :: Int -> t -> t
instance List AsList where
    nil = AsList []
    cons h (AsList t) = AsList (h : t)
mylist :: List t => t
mylist = cons 3 (cons 6 nil)

In this way we transform our data structures into generic computer programs that are interpreted to output our data structures.

This post isn't really about tagless final style so I won't go into too much more detail. Really this post is about Scott encodings.

There is a funny little Combinator known as Mu which can be used to encode recursion in a tricky way.

newtype Mu f = Mu (forall a. (f a -> a) -> a)

Of course in Haskell you don't really need such a cumbersome encoding. This is just theory.

I have found it useful on occassion to box up tagless final data on occasion even though you are not really supposed to.

newtype Box k = Box (forall a. k a => a)

Notice something? In the core language type classes are desugared to record parameters implicitly passed in. So Box is just a funny variant of Mu!

There is another well known way of encoding recursion.

data Nu f = forall a. Nu a (a -> f a)

This is suggestive of another style of encoding.

class Stream t where
    hd :: t -> Int
    tl :: t -> t

data CoBox k = forall a. k a => CoBox a

And indeed this works fine.

toList :: CoBox Stream -> [Into]
toList (CoBox x) = loop x where
    loop x = hd x : tl x

Tagless "final" style is revealed for what it really is. A style of open recursion based around functors.

This is suggestive of a new approach.

class Stream f where
   hd :: f a -> Int
   tl :: f a -> a
   cons :: Int -> a -> f a

newtype Fix f = Fix (f (Fix))
toList :: Stream f => Fix f -> [a]
toList (Fix x) = hd x : toList (tl x)

But this is a digression for another time.

Recursion, corecursion and thunks

Molossus Spondee — Thu, 18 Jun 2020 15:16:16 +0000

Java does not support tail calls.

The usual workaround is a type like the following.

class Thunk<A> {
     boolean isDone();
     Thunk step();
     A finish();
}

Looked at mathematically this type is really a corecursive definition sort of like a stream datatype.

exists b. (b -> (b + a))

It happens there exists a dual recursive datatype.

forall b. ((a -> b) -> (b -> b) -> b

You can apply the math to a simple factorial function like so.

 <C> C fact (int m, int n, Function<Supplier<C>,C> y, Function<Integer, C> result) {
     if (n < 1){
          return h.apply(m);
     }
     return y.apply(() -> fact(m *n, n -1, y, h));
}

At first it appears we have gained nothing from this approach except a degree of indirection. But in fact this lets us delay and thunk an evaluation step or just evaluate it directly.

I'm still not sure this is the best approach for tail calls on the JVM but I remain hopeful recursion schemes will bring a better answer than the ordinary one.

If you could add one new instruction to mainstream hardware what would it be?

Molossus Spondee — Fri, 12 Jun 2020 17:01:05 +0000

Similar to Agner Fog's idea of a new instruction set architecture but much less limited in scope https://www.agner.org/optimize/blog/read.php?i=421 if you could add one entirely new instruction to mainstream hardware what would add? I'll write some of my own thoughts below as a comment but I'm interested in what the rest of the developer community would want. Are there things you just can't do without adding a dedicated instruction or things that are just too slow? Or perhaps it is more of a convenience thing or some other factor I have not considered?

Java polymorphism workaround

Molossus Spondee — Thu, 21 May 2020 20:44:33 +0000

One limitation of Java generics is that you can't have polymorphic data within a method. But there is a workaround of declaring a static class within a method. The Java record syntax let's you do this without creating a new inner class object. Hopefully the inner class limitation on classes declared inside a method is lifted.

int myfunction(int x) {
   record Id() {
       static <A> id(A input) {
           A value = input;
           return value;
       }
   }
   return Id.id(x);
}

It's a bit awkward but sometimes useful in heavily polymorphic code.

Equality Constraints With Java

Molossus Spondee — Sun, 17 May 2020 14:52:26 +0000

final class Subclasses<A extends B, A>{
}
record Equals<A, B>(Subclasses<? super A,B> left, Subclasses<? super B, A> right){}

Reifies equality constraints

Well and truly uninstantiable Java classes

Molossus Spondee — Fri, 15 May 2020 03:38:33 +0000

public class Privileged {
    public Privileged(){
        super();
        checkPermissions();
    }
}

Is insufficient due to tricks with race conditions.

public class Privileged {
    public Privileged(){
        this(checkPermission());
    }
    private Privileged(Void dummy) {}
}

Is the proper procedure

Teleogical Programming

Molossus Spondee — Sun, 03 May 2020 17:10:57 +0000

I would comment an exceptional use of exceptions but probably would not stress over such a decision otherwise.

I try to think about programming concepts in a descriptive rather than a prescriptive fashion.

For example, I prefer "const variables in C permit the type checker to disallow writes and possibly link static constants into read only sections" over "a const variable in C is prescribed for read only purposes."

Compilers do not understand the intent behind variable names and they do not understand the intent behind for loops, goto, exceptions and all the rest of program structure. Compilers do not even understand the intent of the language designer. Compilers only do what they were programmed to do.

Sometimes teleogical thinking is important such as for understanding what uses of an API are supported but I try not to get locked into it.

Being locked into a language or API designer's vision also locks you into their mistakes. Dennis Ritchie is not an authority on the correct or permitted use of for loops. There is no correct or prescribed use of for loops just only what for loops actually do. What classes or any other language construct ought to be used for is a similarly pointless discussion.

I try to see things for what they are not what they ought to be.

Exceptions are not for exceptional conditions. Exceptions are a syntax construct. Teleogical thinking mistakes programming languages for human languages. Describing what a program is intended to do is for comments.

Never Inline Hack Java

Molossus Spondee — Fri, 03 Apr 2020 23:50:59 +0000

As of occasion you may need to ensure some Java code is never inlined when debugging performance problems.

The following hack works around this by abusing a special exception for the Throwable constructor.

static T dontinline(Supplier supplier) {
return (T) new Throwable() {
Object sneak = supplier.get();
}.sneak;
}

Nevertheless, Molossus Spondee Coded

Molossus Spondee — Tue, 03 Mar 2020 20:19:18 +0000

be me
be born in Vancouver
high cost of living
dirt poor
second son of the family
my dad was a failed starving artist
my mother worked at data entry at a bank
she was fat with a broken back
and at home they didn't do much but eat and watch TV
I mostly grew up alone on books and the computer
at school I was never really bullied
I'd come home and my parents would ask
Were you bullied today at school?
Nothing happened at school
I just hid behind the back at lunch and did nothing
all of my life just nothing
I got a job below my skills and paid my way through college
but the rage ate away at me
I would walk along the streets for hours
just walking away the rage
I had violent and suicidal and sexual and jealous thoughts
I began to suffer at college
I sat in a haze at the library through exams for courses I hadn't been to all semester
but I pushed through
I got an Associate's Degree in CS
I worked part time 10 hours a week
barely
are a job that didn't really use my skills
at night I would feel like I was choking on the smell of burning garbage
so I would go for long walks
I started writing poetry
just sitting at the library and writing poetry all day
I developed weird pains through out my body
I always had body issues
and when I was 24 I got badly sunburned
I freaked out and went to the emergency room
fully convinced I was dying of skin cancer
I kept going on in a fog
in pain and suicidal everyday
I was convinced my face was swelling up oddly
it was round about a year after that
I began meditating
and it really saved my life
I became really accomplished
I meditated a lot
I had to because I was in so much pain
but soon the choking rage came back
eventually I bought a skirt
and it was when I put it on I had to admit I was trans

There's no conclusion here except maybe things didn't have to be like this and you don't really know what handicaps people are struggling with just by looking at their skin or apparent gender and I don't really believe in bad guys and punishment anymore. When you've been to that point where you're a danger to yourself and others you know it's already punishment enough.

Things are getting better. I'm working more. I hope I'll be able to get a job making real use of my coding skills eventually.