Enumerable
code i mentioned back here.( Read more... )
Enumerable
code i mentioned back here.Applicative
instance has to exhaustively list all of the options! due to the way it works, it ends with a big nested list that ultimately contains one of each possible permutation. like, the code works and all it's just got abysmal space/time complexity. even something as simple as enumerating color space (a paltry 3.6 million options in the space i'm using) would make it lag and freeze.<<$>>
and <<*>>
which work just like <$>
and <*>
save that they require the function to have its first argument be a monoid (and thus by implication require all arguments to be monoids), and using some TRICKERY they manage to store function application in slices that are later combined togetherpick
as kind of arbitrary but it turns out it's actually super importanttotal :: Enumerable a -> Integer
pick :: Monoid a => Enumerable a -> Integer -> Either EnumerableError a
[a]
which is kind of annoying since that’s basically never what you’d actually want)Arbitrary
instance that just did not terminate, since these are nested data structures that can store an arbitrarily complex expression. even after limiting it a bunch i still can get it to churn out nice compact expressions that have a total count of, for example, 4585754857777496571030203272874303312932Applicative
instance is like ~250 charactersPRIMORDIAL [ name: ĉoŝŝaŭp the first element: cosmic ] SPECIES [ species: naŭujĥteŭll raw species: hornet name: naŭujĥteŭllmans element: water description: average-sized humming hornets with an exposed heart with the horns of a frog with a armored ears with a glass cube for a head ] SPECIES [ species: kraken raw species: kraken name: the kraken element: life description: tiny playful kraken covered with moss and shelf fungus with the fangs of a rat with a two-headed ears that are perpetually bleeding ] GOD [ element: water domain: fresh water description: a rusted dodecahedron surrounded by blue eyes ] GOD [ element: light domain: colors description: a exploded octahedron surrounded by white flames ] SPECIES [ species: ogre raw species: ogre name: the ogres element: water description: gigantic glowing ogres who live in the ocean with a hollow prism for a head with gaping udders on their chest with a black pyramid within a iridescent cube within a iron octahedron within a ancient dodecahedron for a head ]
VMap a -> VMap b
(for some concrete type a
and b
) and then i write some code that maps across the vmap (that being the data store i use to store all the rhombic data; it's basically a vector with some extra indexing functions so i can relabel all the coordinates in O(1) time) to look up all the adjacent cells and do whatever i want with the neighbor data that turns up. this is a huge bottleneck in the code, for reasons still unknown to me but probably having to do with laziness, and it's also super awkward to write.=>>
/ extend
. if i have a vmap, then an actual extend function would be extend :: (VMap a -> b) -> VMap a -> VMap b
, which isn't useful -- there's a reason that post talks about zippers, and that's because a zipper has a coherent and justifiable value to give to extract :: Comonad m => m a -> a
, and that's the currectly-selected value. if you don't have a zipper, you gotta pick something arbitrary, and there's no coherent way to write cojoin
/ duplicate
.=>>
, coreturn
, and cojoin
as the comonad class names; the actual Control.Comonad library uses extend
, extract
, and duplicate
.)extend
function: extend :: ([(RD Integer, a)] -> b) -> VMap a -> VMap b
(or _extend :: Coordinate i f v => ([(i, a)] -> b) -> VMapI i a -> VMapI i b
for the still-unfinished arbitrary-index version)extend :: Comonad m => (m a -> b) -> m a -> m b
makes sense, a type that provides a comonad context that can be reduced down to a single value, only to have that reduced value slotted pack into place -- and thus a type where there's some kind of positional or locational data associated with the type itself (and potentially with each value too), among other kinds of "context".Data.Aeson
and Text.JSON
despite how they both do the exact same thing (codify json in haskell). so aeson is... either hooked up into happstack natively, or at least much _easier_ to hook up into happstack, but w/e when i was putting this together i didn't know any of that.)Data.Aeson.encode . Text.JSON.encode
, and i only noticed i did this -- and that it was weird -- when i started digging into the specific guts of the event api, since... if i output null
it would come out as "null"
, and the more complex events were a mess of backslashes due to being escaped into a string. and i had to manually call JSON.decode
on the javascript end.)ToJson
(from aeson) instance for JSObject
(from text.json), just transliterating one form of json encoding to another one. probably at some point i should go in there and pull out all the text.json bits & get rid of that dependency.)Vector
s with a k -> Int
indexing function. a lot of operations go from O(n) or O(log n) time to O(1), which is nice, and important given that the small maps contain ~16k keys and the large maps contain an (unnecessarily large) ~440k keys. actually they only need to store ~23k keys, so uh that is up there on the to-do list also: more efficient sampling of neighboring chunks when generating geometry. the only real downside of using Vector
s over Map
s is that i'd have to write my own union/intersection code, instead of depending on Data.Map
s eight million variants.Data.Map
to store, uh, cubic chunks of coordinates, and then doing a whole lot of key updating to move them around. so roughly half the runtime is taken up by me just shifting thousands upon thousands of keys around when that's an operation that i could be doing in O(1) time with a data structure better-suited. like a big fixed-size array with random access and a single displacement value would handle most of my common operations (shift-all-keys, look up one key) in O(1) time.{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies,
OverlappingInstances,
UndecidableInstances, TypeFamilies,
TypeOperators, ViewPatterns, FlexibleContexts #-}
module Generation.Layer.Render
( Extract(extract)
, render
, (?)(..)
, Term (..)
, Extend (..)
) where
import Prelude hiding (map)
import Data.Map
render :: Extract from (Map k v) => from -> (v -> r) -> Map k r
render t f = map f . extract $ t
infixr 5 ?
data a ? b = a :? Maybe b
class Extract from result where
extract :: from -> result
instance (Term from k v) => Extract from (Map k v) where
extract = final
-- OVERLAPPING
instance (Extend from from' j k v, Extract from' (Map j v'), Show k, Ord k) => Extract from (Map k (v' ? v)) where
extract v = case next v of
(rs, n) -> n `unify` (rekey v) (extract rs)
class Term t k v | t -> k v where
final :: t -> Map k v
class Extend e t j k v | e -> t j k v where
next :: e -> (t, Map k v)
rekey :: e -> Map j a -> Map k a
unify :: (Ord k, Show k) => Map k a -> Map k b -> Map k (b ? a)
unify = mergeWithKey
(\_ a b -> Just (b :? Just a))
(mapWithKey $ \k b -> error $ "unify: bad generation @ " ++ show k ++ ".")
(map $ \b -> b :? Nothing)
Show
instances aren't really needed except for when i crash on a bad generation, b/c uhhhh it seemed like i wanted at least some vague detail if that situation ever crops up)Extract
type class with a single function, extract
. this type class is let's say creatively instanced so that i can extract any depth of generator (the Term
and Extend
typeclasses) into a set of values. this makes it possible to write a render
function that takes any extractable value (i.e., any generator stack regardless of depth) and a function that renders based on those values, while still typechecking to make sure the types match. (previously: i needed separate functions for each depth of generator){-# LANGUAGE MultiParamTypeClasses, FlexibleInstances,
UndecidableInstances, TypeFamilies #-}
class Appl fun arg t where
appl :: fun -> arg -> t
instance (a ~ a') => Appl (a -> b) a' b where
appl = id
instance {-# OVERLAPPING #-} Appl fun arg (b -> t) => Appl fun (b, arg) t where
appl f (n, rs) = appl f rs n
class Appr fun arg t where
appr :: fun -> arg -> t
instance (a ~ a') => Appr (a -> b) a' b where
appr f = f
instance {-# OVERLAPPING #-} (a ~ a', Appr fun arg t) => Appr (a -> fun) (a', arg) t where
appr f (a, x) = appr (f a) x
render*
functions in this code, which is a more complicated step, but now one i'm a lot more confident that i can figure out.)parsec
(which i guess is actually in base
?? haskell's base is so weird)spaces
basically everywhere.appl1 :: (a -> t) -> a -> t
appl1 = id
appl2 :: (a -> b -> t) -> (a, b) -> t
appl2 f (a, b) = appl1 (f a) b
appl3 :: (a -> b -> c -> t) -> (a, (b, c)) -> t
appl3 f (a, b) = appl2 (f a) b
appl4 :: (a -> b -> c -> d -> t) -> (a, (b, (c, d))) -> t
appl4 f (a, b) = appl3 (f a) b
appl5 f (a, b) = appl4 (f a) b
appl6 f (a, b) = appl5 (f a) b
-- etc
appr1 :: (a -> t) -> a -> t
appr1 = id
appr2 :: (a -> b -> t) -> (b, a) -> t
appr2 f (n, rs) = appr1 f rs n
appr3 :: (a -> b -> c -> t) -> (c, (b, a)) -> t
appr3 f (n, rs) = appr2 f rs n
appr4 :: (a -> b -> c -> d -> t) -> (d, (c, (b, a))) -> t
appr4 f (n, rs) = appr3 f rs n
appr5 f (n, rs) = appr4 f rs n
appr6 f (n, rs) = appr5 f rs n
-- etc
class Splittable a b c | a -> b c where
_fst :: a -> b
_snd :: a -> c
instance Splittable (a, b) a b where
_fst = fst
_snd = snd
pair :: Splittable a b c => a -> (b, c)
pair a = (_fst a, _snd a)
applg1 :: (a -> t) -> a -> t
applg1 = id
applg2 :: Splittable s a b => (a -> b -> t) -> s -> t
applg2 f (pair -> (a, b)) = applg1 (f a) b
applg3 :: (Splittable s a s', Splittable s' b c) => (a -> b -> c -> t) -> s -> t
applg3 f (pair -> (a, b)) = applg2 (f a) b
applg4 f (pair -> (a, b)) = applg3 (f a) b
applg5 f (pair -> (a, b)) = applg4 (f a) b
applg6 f (pair -> (a, b)) = applg5 (f a) b
apprg1 :: (a -> t) -> a -> t
apprg1 = id
apprg2 :: Splittable s a b => (b -> a -> t) -> s -> t
apprg2 f (pair -> (n, rs)) = apprg1 f rs n
apprg3 :: (Splittable s a s', Splittable s' b c) => (c -> b -> a -> t) -> s -> t
apprg3 f (pair -> (n, rs)) = apprg2 f rs n
apprg4 f (pair -> (n, rs)) = apprg3 f rs n
apprg5 f (pair -> (n, rs)) = apprg4 f rs n
apprg6 f (pair -> (n, rs)) = apprg5 f rs n
render :: (Extend (Extend (Extend ...) v') v) -> (... ? v' ? v -> t) -> Map k t
except i can't even come close to formulating what that type would look like. especially given Extend
isn't a type but instead a typeclass.instance (Ord k, Monad m, Generator a m k u) => Generator (Layer a u m k v) m k v where
tiltRandomly :: (a, a) -> Plane a -> Rand g (Plane a)
tiltRandomly (lo, hi) p =
if (lo > hi)
then error "tiltRandomly: lo > hi"
else case (listToMaybe . liftM catMaybes . sequence . repeat $ do
v <- V2 <$> randomR (0, hi) <*> randomR (0, hi)
if magnitude v <= hi && magnitude v >= lo
then $ Just v
else Nothing) of
Just v -> return $ tilt v p
Nothing -> error "tiltRandomly: uh wow that infinite list sure evaluated fast huh"
i think this is the first time i've explicitly used laziness to my advantage
but of course it's in a messy partial function. also, bad news if you set lo
& hi
such that it takes like eight million tries to get a value that passes! laziness sure is a thing.
so i wrote basically one good, general-purpose Haskell Code post on tumblr, so i figured i could fix it up a little and post it over here too. it is i guess somewhat monad tutorial fallacy-y, but it's not really about monads.
it's about the applicative hierarchy! this is a set of three typeclasses: Functor
, Applicative
, and Monad
, in that order. each of these typeclasses has a lifting function, and all but Functor have a unit function.
(the unit function is a -> f a
, so just something that takes an existing value and places it inside the functor. it's called pure
in Applicative
and return
in Monad
. specific Functor
s will generally have ways to put values inside them, of course -- List
has :
and Maybe
has Just
, for example -- but they're not considered essential to the typeclass as they are in Applicative
or Monad
. this is i think a quirk of haskell's history, and not really anything reflective of underlying category-theory gibberish.)
Functor
's lifting function is Functor f => (a -> b) -> f a -> f b
and is called fmap
Applicative
's lifting function is Applicative f => f (a -> b) -> f a -> f b
and is called <*>
or apMonad
's lifting function is Monad f => (a -> f b) -> f a -> f b
and is called =<<
or bindthe big takeaway here is that you can (and should) think of these as variations on a theme: assuming you want a function f a -> f b
, each one takes one function of varying power and turns it into a function across values of your functor.
it is like you are saying "hey, i want a f a -> f b
function, but i don't really want to write all that context-handling code myself. isn't there an easier way?" and it turns out that there can be, if you don't actually care that much about the context!
the reason why this is a "hierarchy" rather than just being three typeclasses each doing a similar thing is that each of these classes is strictly more powerful than the ones that come before it, in a very precise sense: using each class's lifting function, you can recreate the lifting functions of the lower classes.
fmap
can be said in Applicative
as (<*>) . pure
<*>
can be said in Monad
as \mf mv -> (\f -> (\v -> return $ f v) =<< mv) =<< mf
(there are more concise, less readable ways to put that)practical applications:
fmap
only cares about the values in the functor, not the context itself. if you just want to change the values inside the functor, this is the lifting function to use. since this doesn't alter the functor context, there's generally a pretty clear correspondance between values before and after the function application (the values in a list will remain in the same order, for example)<*>
is useful when you have a function that, itself, is inside a functor context. what this does is uses the functor context to inform the functor context and the value context to inform the values -- there's no crosstalk allowed: if you have Maybe a
and Maybe (a -> b)
, the functor context depends entirely on whether they're both Just
, and not at all on the actual values. and the values depend entirely on the function, and not at all on the functor context. having a function inside a context might not seem like a common occurance, but the big use is multi-argument functions. fmap
is all well and good when you have a one argument function of the form a -> b
, but if you try to fmap something with a type signature of a -> b -> c
things get messy. you end up with something like f (b -> c)
, which is basically useless in Functor
. except then <*>
comes along and lets you transform that into a function f b -> f c
, which is wayyy more useful. this works indefinitely, for as many arguments as you want -- fmap
works on 1-argument functions, but fmap
plus <*>
works on n-argument functions. (fmap
with an Applicative
constraint is called <$>
, and you usually see it in places like (*) <$> [1,2,3] <*> [4,5,6]
, or to construct a type with a constructor when your values are all inside some Applicative
)=<<
is useful when you care a little about the output functor context. maybe you're looking up values from a table, so you might want to have a Maybe a
value on output. maybe you're splitting things into lists, so you want to have a [a]
value on output. and then it turns out you're also using Maybe
or []
values on input! using fmap
would get you something like Maybe (Maybe a))
or [[a]]
, and you don't care about that extra layer of depth. On lists, =<<
is a lot like \f -> concat . fmap f
some examples:
> fmap (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
the input and output lists are the same length: fmap
is incapable of changing "functor context", which here means "list length".
> [(* 2), (+ 1)] <*> [1..10]
[2,4,6,8,10,12,14,16,18,20,2,3,4,5,6,7,8,9,10,11]
and here we see that the Applicative
"context" for lists says to treat them like cartesian joins: each list item is applied to each list item in the other list. so we can alter the "functor context" (read: list length) of the result, but only in ways that naturally follow from the functor context of the arguments. in this case, 2 items * 10 items = 20 items.
> (\x -> replicate x x) =<< [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]
and here, since we're creating a new "functor context", we can make the resulting list any length we want.
some minutiae:
Functor
, and then there was Monad
. it was only later that people realized Applicative
was there and was useful, and so we ended up in this situation where instancing something to Monad
required a Functor
instance, but not an Applicative
, despite every Monad
also being an Applicative
.bind
: in haskell, bind
is >>=
, which has the arguments the other way around (so, f a -> (a -> f b) -> f b
); i feel like this obscures the actual properties of the bind operation and so for that and other reasons i tend to use =<<
instead. in practice, =<<
composes "backwards", in that you have to read it from right-to-left to figure out how a value is transformed. to me, that's fine -- that's also the way function composition works, and it's better to always read right-to-left than to switch back and forth depending on whether you're using monads or not. but the do-notation uses >>=
because it gets a left-to-right, top-to-bottom reading, and a lot of people use >>=
generally for the same reason.Applicative
's version of fmap
, <$>
. Monad
has liftM
for fmap
and ap
for <*>
. generally it's considered good practice to use whichever version carries the least constraints. if you only need to fmap
something, it's preferred to just use fmap
instead of liftM
, unless you're already working under a Monad f =>
constraintIO
monad, because that's the monad that gets the most use, and is the one everyone has to deal with first. IO
is deeply magical for reasons i'm not going to get into, and that most 'monad tutorials' cover. Monad
is just a typeclass, like any other typeclass, and it can be understood generally. in general one can only operate on a monadic value inside monadic code, but a lot of the time you can do things like pattern-match on a constructor, or use functions like fromMaybe
to pull "monadic" values out into the rest of your code to, in essence, get a m a -> a
function. this is fine. but not all monads let you do it; this depends less on "monads" and more on the specific type you're using (that happens to have a Monad
instance)