603 karma · joined September 11, 2013
I'm not making a value judgement whether this is utopian or dystopian but imagine streaming money. Instead of paying for the use of something in advance and in coarse-grained chunks (driving through a tunnel, running on a treadmill in a gym, watching netflix, parking somewhere, etc...) you'd instead stream money throughout usage. On-demand with continuous settlement for the duration.
It would make me happy to be wrong but I envision even more inequality as a result of brexit. I just don't see it playing out in any way that would result in an objectively better quality of life for working people. Ironic how I, a highly paid immigrant, am concerned for their future.
- modules:
- { name: [Data.List], as: List }
- { name: [Data.Map, Data.Map.Strict], as: Map }
and then you get a hlint warning if you use DL/DMS instead of List/Map type FooContext m = (GetTime m, GenUUID m, Log m, Auth m, ReadDB m, WriteS3 m, BarApi m, etc...)
foo :: (FooContext m) => UUID -> m Foo
The main downside is ergonomics, ie. the amount of boilerplate needed, but personally I don't think that's a high price to pay.To elaborate this point I'd say that the most important practical use of all that "monad mumbo-jumbo" in Haskell is that you can tag your functions with what they can and can't do and then the type system tracks this for you:
-- pure function
f1 :: Text -> Int
-- can fail
f2 :: Text -> Maybe Int
-- can read from some MyEnv record
f3 :: Text -> Reader MyEnv Int
-- can keep a set of bool as state around
f4 :: Text -> State (Set Bool) Int
etc... and of course to go nuclear: -- can do anything
f5 :: Text -> IO Int
The tracking part is that you can't call f5 from within f1, the type checker says no. It enforces separation between all these various effect boundaries.Also we don't have to stop here. A natural next step is defining exact effects one is after. For example say I want my function to be able to get some entity from a DB:
-- any type that is an instance of Entity can identify itself by uuid
class Entity e where
identify :: e -> UUID
-- The effect we want, ie. get an entity via its uuid
class (Monad m, Entity e) => GetEntity e m where
getEntityById :: UUID -> m (Maybe e)
now we can say things like: data User = MkUser {uId :: UUID, uName :: Text}
-- a User can identify itself
instance Entity User where
identify = uId
-- as User is an Entity so we can get it via its uuid (if it exists)
getUserById :: (GetEntity User m) => UUID -> m (Maybe User)
getUserById = getEntityById
Also notice how getUserById does not say anything about IO or a DB. All it states is that whatever context it will run in that context must know how to get a user via its uuid. You can then plug in whatever actual context you want, say: newtype Prod a = MkProd {unProd :: ReaderT ProdDB IO a}
deriving newtype (Functor, Applicative, Monad, MonadReader ProdDB, MonadIO)
-- get a user from a DB for real
instance GetEntity User Prod where
getEntityById :: UUID -> Prod (Maybe User)
getEntityById eid = do
ProdDB {..} <- ask
-- query the DB, etc...
or newtype Mock a = MkMock {unMock :: State (Map UUID User) a}
deriving newtype (Functor, Applicative, Monad, MonadState (Map UUID User))
-- get a user from a mock DB
instance GetEntity User Mock where
getEntityById :: UUID -> Mock (Maybe User)
getEntityById eid = gets (Map.lookup eid)
All in all the programmer have fine-grained control over what various parts of their code can or can't do.The term I'd use (at least from the top of my head) is hygiene. The article uses the word safety in a restrictive sense, ie. preventing errors. Forcing iFoo instead of foo, to me, is more about hygiene where one could still potentially make an (accidental or deliberate) error but that would go against said hygiene. Maybe another way to put it is that safety prevent misuse while hygiene guides correct use. Or another is that with safety the letter and spirit of the law are one and the same while with hygiene it's not.
Haskell's `newtype` is an amazing tool for (proactive) hygiene and, as the article says, a limited tool for safety. By proactive hygiene I mean that if you have:
bmi :: Float -> Float -> Float
Looking at it you don't know what those params are. They are all just `Float`s. There's not vocabulary to them. Meanwhile here: newtype Height = MkHeight Float
newtype Weight = MkWeight Float
bmi :: -> Height -> Weight -> Float
It is both clear what they are as well as the compiler will prevent you from passing `Weight` as the 1st param. Now it's not safety as you can still wrap the wrong `Float` as `Height` but that would go against the hygiene.[1] https://bitcointalk.org/index.php?topic=583.msg11405#msg1140...
[2] http://p2pfoundation.ning.com/forum/topics/bitcoin-open-sour...
Compositional sure, but performance? Care to elaborate?
Compare the Functor instances of the original inductive Tree type with TreeShape a:
instance Functor Tree where
fmap :: (b -> c) -> Tree b -> Tree c
fmap f (Leaf v) = Leaf (f v)
fmap f (Node l r) = Node (fmap f l) (fmap f r)
instance Functor (TreeShape a) where
fmap :: (rec -> b) -> TreeShape a rec -> TreeShape a b
fmap _ (Leaf v) = Leaf v
fmap f (Node l r) = Node (f l) (f r)
You see that in the latter the function we map over acts on the rec type which is the induction we factored out and is only present in the Node case. You can view the Leaf case as the termination case where Fix stops expanding. It's useful to write out the evaluation by hand on a small example to see how it works.> I'm also curious about "the compiler is more than happy to do it for us" - is that in the form of `deriving Functor`?
It is indeed the deriving Functor. You can even examine what the compiler does by dumping out the instance using the -ddump-deriv flag.
For more background reading as to why this is possible here are a few links:
- https://mail.haskell.org/pipermail/libraries/2011-February/0...
- https://www.schoolofhaskell.com/user/edwardk/snippets/fmap
> I have never seen stock before!
It comes from the DerivingStrategies lang extension which makes it explicit that this derivation is "built in". Everything works the same without it though so we can just ignore it as well.
> Lastly, does `processFunctor` exist in the standard library?
If by standard you mean the Prelude then no, but there are tons of packages, eg.:
- https://hackage.haskell.org/package/data-fix
- https://hackage.haskell.org/package/recursion-schemes
1. Let's define a simple binary tree and a (recursive) function to process it:
data Tree a
= Leaf a
| Node (Tree a) (Tree a)
processTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
processTree processLeaf processNode = walk
where
walk (Leaf v) = processLeaf v
walk (Node l r) = processNode (walk l) (walk r)
processTree takes 2 functions, namely the "how to process a leaf?" and the "how to process a node?" ones as well as a tree and then... processes it :) Now, given a tree of Ints, we can use the above to eg. sum its values, find the biggest one or count the nodes: λ> myTree = Node (Node (Leaf 3) (Leaf 9)) (Leaf 7)
λ> processTree (+ 1) (+) myTree
22
λ> processTree id max myTree
9
λ> processTree (const 1) (+) myTree
3
Great. Now, instead of defining the above Tree type as an inductive type, let's factor that part out: data TreeShape a rec
= Leaf a
| Node rec rec
This type is kinda like the original except we add a new type variable (rec) for the inductive part. Ok, now comes the interesting (crazy?) part: Let's define a weird type called Fix: newtype Fix f = Fix {unFix :: f (Fix f)}
Don't get lost in it! Just read on. Let's use this weird Fix type to define our original Tree type as such: type Tree a = Fix (TreeShape a)
Also let's rewrite the original processTree function using this new type: processTree :: (TreeShape a b -> b) -> Tree a -> b
processTree process = walk
where
walk (Fix (Leaf v)) = process (Leaf v)
walk (Fix (Node l r)) = process (Node (walk l) (walk r))
Looks kinda like the original except that it now uses the same(!) function (aka. algebra) to process both leaves and nodes. This allows us to write simple (non-recursive) functions: sum (Leaf v) = v
sum (Node l r) = l + r
max (Leaf a) = a
max (Node l r) = max l r
size (Leaf _) = 1
size (Node l r) = l + r
and recover: λ> myTree = Fix $ Node (Fix $ Node (Fix $ Leaf 3) (Fix $ Leaf 9)) (Fix $ Leaf 7)
λ> processTree sum myTree
19
λ> processTree max myTree
9
λ> processTree size myTree
3
At this point you might rightfully ask: Why oh why would we go through all this suffering just to recover the same functionality we had originally? Good question :) To answer it we need to realise that "TreeShape a" (and thus also "Tree a") is a member of a class called Functor, which means it knows how to map functions over itself. The magic incantation to do such mapping is called fmap in Haskell. Let's make TreeShape work with fmap: instance Functor (TreeShape a) where
fmap _ (Leaf v) = Leaf v
fmap f (Node l r) = Node (f l) (f r)
Now, knowing the above, we can rewrite our processTree function into a _much_ more generic form that works not just on our Tree type but on _any_ Functor: processFunctor :: Functor f => (f b -> b) -> Fix f -> b
processFunctor process = process . fmap (processFunctor process) . unFix
This processFunctor function (aka. catamorphism) has no notion of the shape it processes other than that shape should know how to map a function over itself (ie. it's a Functor). As an added bonus we don't even need to write Functor instances for our types by hand as deriving them is a deterministic and mechanical process and thus the compiler is more than happy to do it for us: data TreeShape a rec
= Leaf a
| Node rec rec
deriving stock Functor
To summarise: if we want to process some recursive data structure and that data structure happens to be a Functor then all we need to do is derive it's functor instance, write a simple function to do something with an element of the structure and apply that function to the whole using processFunctor.I'm assuming you are referring to Haskell? It's a general purpose programming language so of course it handles state, branching, etc...
data Tree a = Empty | Leaf a | Node a [Tree a]
deriving stock (Show, Functor, Foldable, Traversable)
label :: Tree a -> Tree (a, Int)
label t = evalState (traverse f t) 0 where
f t' = state (\c -> ((t', c), c + 1))
The above code labels nodes of a multiway tree using a counter. State and branching.https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
Here is a teaser, the 1st table:
Build system | Persistent build information | Scheduler | Dependencies | Minimal | Cutoff | Cloud
Make | File modification times | Topological | Static | Yes | No | No
Excel | Dirty cells, calc chain | Restarting | Dynamic | No | No | No
Shake | Previous dependency graph | Suspending | Dynamic | Yes | Yes | No
Bazel | Cloud cache, command history | Restarting | Dynamic(∗) | No | Yes | Yes
which shows that Excel can be viewed as a dynamic build system!So is Haskell. What I'm saying is that in 2020 the dev workflow is not: code, compile, run, repeat. Thanks to modern tooling it is now a near-instant feedback loop of: code, red wiggly line(s), fix, repeat. Ie. real-time conversation with the compiler.