Are free monads also zippily applicative?
I think I've come up with a "zippy" Applicative
instance for Free
.
data FreeMonad f a = Free (f (FreeMonad f a))
 Return a
instance Functor f => Functor (FreeMonad f) where
fmap f (Return x) = Return (f x)
fmap f (Free xs) = Free (fmap (fmap f) xs)
instance Applicative f => Applicative (FreeMonad f) where
pure = Return
Return f <*> xs = fmap f xs
fs <*> Return x = fmap ($x) fs
Free fs <*> Free xs = Free $ liftA2 (<*>) fs xs
It's sort of a ziplongest strategy. For example, using data Pair r = Pair r r
as the functor (so FreeMonad Pair
is an externally labelled binary tree):
+++ +++ +++
    <*>  
+++ h x +++ > +++ +++
       
f g y z f x g x h y h z
I haven't seen anyone mention this instance before. Does it break any Applicative
laws? (It doesn't agree with the Monad
instance of course, which is "substitutey" rather than "zippy".)
1 answer

From the definition of
Applicative
:If
f
is also aMonad
, it should satisfypure
=return
(<*>)
=ap
(*>)
=(>>)
So this implementation would break the applicative laws that say it must agree with the
Monad
instance.That said, there's no reason you couldn't have a newtype wrapper for
FreeMonad
that didn't have a monad instance, but did have the above applicative instancenewtype Zip f a = Zip { runZip :: FreeMonad f a } deriving Functor instance Applicative f => Applicative (Zip f) where  ...
See also questions close to this topic

Haskell List functions
I was wondering why in Haskell there are not symmetry in some function names:
For example:
head
: get the first elementlast
: get the last element
Is there good reason why for example
head
function was not namedfirst
, or the other way around last
function could be namedend
or something similar. 
How to wrap monadic action in IO
I am trying to treat a
ReaderT X IO
monad as IO to achieve the following: this is the monad I defined: type Game = ReaderT State IO runGame :: State > Game a > IO a runGame state a = runReaderT a state readState :: Game State readState = ask  some IO action, i.e. scheduling, looping, etc. ioAction :: IO a > IO () ioAction = undefined  this works as expected, but is rather ugly doStuffInGameMonad :: Game a > Game () doStuffInGameMonad gameAction = do state < readState liftIO $ ioAction $ runGame state gameAction
ioAction
for example is scheduling another IO action in intervals. Unwrapping theGame
monad every time seems a bit cumbersome  and feels wrong.What I am trying to achieve instead is:
doStuffInGameMonad :: Game a > Game () doStuffInGameMonad gameAction = ioAction $ gameAction
My intuition tells me, this should be possible somehow, because my
Game
monad is aware of IO. Is there a way to implicitly convert/unlift theGame
monad?Please excuse if my terminology is not correct.

doing trivial search and replace via a regex
I am using regextdfa which installs easiely with stack
As seen in the docs, using a regex predicate is simple:
λ> emailRegex = "[azAZ09+._]+@[azAZ]+\\.[az]+" λ> "my email is email@email.com" =~ emailRegex :: Bool
How can I search and replace with this lib ? I would like for example, to filter out characters from a string.
I can't
fmap
on a string with the=~
operator since it expects strings and not characters as input, which is why I am stuck.Many thanks.

Creating a tree structure from a data frame in R
I have just started learning R and am trying to adapt the code found here to import employee data from an Excel file into a data frame and then use the as.node function from the
data.tree
package.This is the code I have written so far
library(data.tree) library(readxl) library(treemap) baseframe < read_excel("Test Emplist.xlsx") baseframe$pathstring < paste("CompanyName", baseframe$SupNum, baseframe$EmployeeNum, sep = "/") stafflist < as.Node(baseframe)
The data frame is being created successfully but when I get to the line
stafflist < as.Node(baseframe)
I am getting an error message sayingError in strsplit(mypath, pathDelimiter, fixed = TRUE :
noncharacter argumentI'm guessing the as.node function calls another function called
strsplit
somewhere. I have tried running the function myself as sostrsplit(baseframe$pathstring, "/", fixed = TRUE)
and it is running no problem. I'm not sure why the as.node function is throwing the error?

Creating a tree from a data frame in R
I have just started learning R and am trying to adapt the code found here to import employee data from an Excel file into a data frame and then use the as.node function from the
data.tree
package.This is the code I have written so far
library(data.tree) library(readxl) library(treemap) baseframe < read_excel("Test Emplist.xlsx") baseframe$pathstring < paste("CompanyName", baseframe$SupNum, baseframe$EmployeeNum, sep = "/") stafflist < as.Node(baseframe)
The data frame is being created successfully but when I get to the line
stafflist < as.Node(baseframe)
I am getting an error message sayingError in strsplit(mypath, pathDelimiter, fixed = TRUE :
noncharacter argumentI'm guessing the as.node function calls another function called
strsplit
somewhere. I have tried running the function myself as sostrsplit(baseframe$pathstring, "/", fixed = TRUE)
and it is running no problem. I'm not sure why the as.node function is throwing the error?

partitioning a highly connected tree into k partitions such that the cuts at the leaf level nodes is minimized
I have say 1 Million nodes numbered 11Million which are connected to say different set of nodes AZ the relationship is 1 to many . Wherein many nodes from set 11Million can be connected to set AZ . Now i want to partition the 11Million in k partitions such that the duplicity of the nodes AZ is minimized in K partitions or putting it other way round making k partitions such that sum of out degree of nodes AZ is minimized . Can someone please help me with the algorithm if they have solved similar problem
I read literature on spectral partitioning etc they seem to be somewhat having high time complexity as well as the code complexity . I would highly appreciate some simple and fast algo

Do monad transformers, generally speaking, arise out of adjunctions?
In Adjoint functors determine monad transformers, but where's lift?, Simon C has shown us the construction...
newtype Three u f m a = Three { getThree :: u (m (f a)) }
... which, as the answers there discuss, can be given an
instance Adjunction f u => MonadTrans (Three u f)
(adjunctions provides it asAdjointT
). Any Hask/Hask adjunction thus leads to a monad transformer; in particular,StateT s
arises in this manner from the currying adjunction between(,) s
and(>) s
.My followup question is: does this construction generalise to other monad transformers? Is there a way to derive, say, the other transformers from the transformers package from suitable adjunctions?
Meta remarks: my answer here was originally written for Simon C's question. I opted to spin it off into a selfanswered question because, upon rereading that question, I noticed my purported answer had more to do with the discussion in the comments over there than with the question body itself. Two other closely related questions, to which this Q&A arguably is also a followup, are Is there a monad that doesn't have a corresponding monad transformer (except IO)? and Is the composition of an arbitrary monad with a traversable always a monad?

Reasoning about stateful and exception(ful) programs in Coq
Here is my goal: I want to reason (in Coq) about programs with state and exception effects. I want to prove properties about the success and the failure of stateful programs. Say: if the program is successful, here is the certified result (with its proof). If the computation of the program failed, here is some data about why it failed and some proof about the failure (this proof may be about the negation of the certification, which in this case may be a view).
The Hoare State Monad (HSM) solved half of my problem.
The HSM is a type
HoareState p a q
, such that the parameters are in order: the precondition, the type of the computed value and the postcondition.I thought that if I just embed the
sum
type inside the HSM would be enough. The new parameterE
is the type representing the failure.Program Definition HoareState (E : Set) (pre : Pre) (a : Type) (post : Post a) : Type := forall i : {t : st  pre t}, {c : sum (a * st) E  match c with  inl (x, f) => post (proj1_sig i) x f  inr _ => True end}.
The complete definition is in an gist, so I don't make this question huge. The operators
return
,bind
,get
,fail
are straightforward to define if you read the HSM paper.This modified HSM has the behavior of state and exception, but it does not provide proofs about the failure, only about the success.
Another problem with this solution is that failure type is just one. If I wish to define a function dealing with different kinds of failures, the only solution is to create a single type representing all of the failures kinds:
Inductive Fail1 : nat > Set :=  fail1 : forall n, Fail1 n. Inductive Fail2 : bool > Set :=  fail2 : forall b, Fail2 b. Inductive AllFail : Set :=  allFail1 : forall n, Fail1 n > AllFail  allFail2 : forall b, Fail2 b > AllFail.
The type
AllFail
can't have arguments, therefore it can't be related with the arguments of the monadic function defined with it. It becomes hard to prove a lemma about a function resulting in a value of typeAllFail
.In order to prove a property about the failure case, then I guess a second postcondition is necessary. This second postcondition may receive the initial state and the error data. Hence:
Program Definition HoareState (E : Type) (pre : Pre) (a : Type) (post : Post a) (post' : E > st > Prop) : Type := forall i : {t : st  pre t}, {c : sum (a * st) E  match c with  inl (x, f) => post (proj1_sig i) x f  inr b => post' b (proj1_sig i) end}.
Again, the complete definition is in a gist.
This solution is almost what I want. I still have the problem of using the same type for all kinds of failure. But the main problem with this definition are the weird errors that
Program
rises when I'm defining some particular functions. I'm trying to use this last definition in a big project and I don't think it is reasonable to ask someone (here) to help me investigate what is going wrong there. Unfortunately I couldn't reproduce the errors in a smaller scenario. In the small tests that I did, this last definition worked fine.One the error that I get is:
Error: Cannot infer the implicit parameter Q2 of bind whose type is "id > Post id ty" in environment:
Which is not very informative.
I'm not attached to this particular monad, I just want one that does the job. I just thought that would be relevant to mention what I have tried. I have read that the Dijkstra Monads generalize the HSM and can handle exceptions. But still, I couldn't understand it yet, even less how to implement it in Coq.
In short, my question is how to formulate in Coq a monad (any monad) that accomplish my goal.

What is the idiomatic way to write this function (which might normally be called filterA)?
I am going through this course.
There is a section for
Applicative
and I am being asked to implement a function with the following behaviour and type  Filter a list with a predicate that produces an effect.   >>> filtering (ExactlyOne . even) (4 :. 5 :. 6 :. Nil)  ExactlyOne [4,6]   >>> filtering (\a > if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. Nil)  Full [4,5,6]   >>> filtering (\a > if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. Nil)  Full [4,5,6,7]   >>> filtering (\a > if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 13 :. 14 :. Nil)  Empty   >>> filtering (>) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. 10 :. 11 :. 12 :. Nil) 8  [9,10,11,12]   >>> filtering (const $ True :. True :. Nil) (1 :. 2 :. 3 :. Nil)  [[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]] filtering :: Applicative f => (a > f Bool) > List a > f (List a)
I have come up with the following implementation, which satifies all the requirements
filtering f as = let x = sequence (f `map` as) y = zip as <$> x z = filter snd <$> y in map fst <$> z
but it feels a bit "round about" to me, and I can't think of a more direct way to do it.
Note: I have expanded into
x, y, z
because it makes it easier (for me) to follow what is happening, and whilst I realize I could express it all on a single line, I do not consider that to be more 'direct' and thus not an answer to my question.Note 2: This course appears to be building up common type classes from fundamental pieces. We started with a custom implementation of
List
followed byFunctor
and nowApplicative
, so I can only use concepts from these classes. I cannot use anything fromMonad
yet. 
Cats ValidatedNec mapN with Case Class Error Types
I'd like to use the Cats
ValidatedNec
data type similarly to the example in the Cats documentation forValidated
in the section Meeting applicative in my case, I'm parsingString
s from a file, validating against an appropriate regex for the field, and then (for several fields) converting to a different data type (assuming the regex matched). However, instead of usingcase object
s which extend a common trait for the invalid results (as in the example), I'd like to usecase class
es (which extend a common trait) so I can include contextual information in the case of failure. Can this be done as simply as calling all the validation methods (putting the results in a tuple), as in thevalidateForm
example, and callingmapN
? I'm getting conflicting errors from Intellij (from IntelliJ, it's telling me the expected and actual parameters tomapN
are the same (though it is still marking it as an error); when runningsbt
on the command line, it doesn't resolve themapN
method. I'm using Scala 2.12.8 and cats 2.0.0M1. Any help would be appreciated! 
Understanding Functions as Applicatives in Haskell
I've recently been trying to learn Haskell with the "Learn You a Haskell" and have been really struggling with understanding functions as Applicatives. I should point out that using other types of Applicatives like Lists and Maybe I seem to understand well enough to use them effectively.
As I tend to do when trying to understand something is I tried to play with as many examples as I could and once the pattern emerges things tend to make sense. As such I tried a few examples. Attached are my notes of several examples I tried along with a diagram I drew to try to visualize what was happening.
The definition of
funct
doesnt seem to relevant to the outcome but in my tests I used a function with the following definition:funct :: (Num a) => a > a > a > a
At the bottom I tried to show the same thing as in the diagrams just using normal math notation.
So all of this is well and good, I can understand the pattern when I have some function of an arbitrary number of arguments (though needs 2 or more) and apply it to a function that takes one argument. However intuitively this pattern doesn't make that much sense to me.
So here are the specific questions I have:
What is the intuitive way to understand the pattern I'm seeing, particularly if i view an Applicative as a container (which is how I view
Maybe
and lists)?What is the pattern when the function on the right of the
<*>
takes more than a single argument (I've mostly been using the function(+3)
or(+5)
on the right)?why is the function on the right hand side of the <*> applied to the second argument of the function on the left side. For example if the function on the right hand side were
f()
thenfunct(a,b,c)
turns intofunct (x, f(x), c)
?Why does it work for
funct <*> (+3)
but not forfunct <*> (+)
? Moreover it DOES work for(\ a b > 3) <*> (+)
Any explanation that gives me a better intuitive understanding for this concept would be greatly appreciated. I read other explanations such as in the book I mentioned that explains functions in terms of
((>)r)
or similar patterns but even though I know how to use the>
) operator when defining a function I'm not sure i understand it in this context.Extra Details:
I want to also include the actual code I used to help me form the diagrams above.
First I defined funct as I showed above with:
funct :: (Num a) => a > a > a > a
Throughout the process i refined funct in various ways to understand what was going on.
Next I tried this code:
funct a b c = 6 functMod = funct <*> (+3) functMod 2 3
Unsuprisingly the result was 6
So now I tried just returning each argument directly like this:
funct a b c = a functMod = funct <*> (+3) functMod 2 3  returns 2 funct a b c = b functMod = funct <*> (+3) functMod 2 3  returns 5 funct a b c = c functMod = funct <*> (+3) functMod 2 3  returns 3
From this I was able to confirm the second diagram is what was taking place. I repeated this patterns to observe the third diagram as well (which is the same patterns extended on top a second time).

Defining Free Bind in a way that is compatible with the Free Monad
So we have the free monad: (encoding may vary, but they're all the same)
data Free f a = Pure a  Impure (f (Free f a)) instance Functor f => Monad (Free f) where pure = Pure Pure x >>= f = f x Impure x >>= f = Impure ((>>= f) <$> x) liftFree :: Functor f => f a > Free f a liftFree x = Impure (Pure <$> x) runFree :: Monad g => (forall x. f x > g x) > Free f a > g a runFree _ (Pure x) = pure x runFree f (Impure x) = join (runFree f <$> f x)
such that
runFree
forms a monad homomorphism, which is the defining property of the free monad.runFree f (pure x) = pure x runFree f (liftFree x >>= liftFree . g) = f x >>= (f . g)  + some other associativity requirements
We can also make a similar construction to (what I believe to be) the free
Bind
from semigroupoids, which is a functor with only bind>>
:data Free1 f a = Done (f a)  More (f (Free1 f a)) instance Functor f => Bind (Free f) where Done x >> f = More (f <$> x) More x >> f = More ((>> f) <$> x) liftFree1 :: f a > Free1 f a liftFree1 = Done runFree1 :: Bind g => (forall x. f x > g x) > Free1 f a > g a runFree1 f (Done x) = f x runFree1 f (More x) = f x >> runFree1 f
and we get the appropriate bind homomorphism:
such that
runFree1
forms a bind homomorphism, which is the defining property:runFree1 f (liftFree1 x >> liftFree1 . g) = f x >> (f . g)  + some associativity laws
Now, these two types are great. We can convert from
Free1
toFree
, which makes sense:toFree :: Free1 f a > Free f a toFree (Done x) = Impure (Pure <$> x) toFree (More x) = Impure (toFree <$> x)
but converting backwards is trickier. To go from a
Free
to aFree1
, we would have to handle two cases: The
Free
is pure, so cannot be represented inFree1
.  The
Free
is impure, so can be represented inFree1
.
It makes sense that these two cases can be handled statically, since we can just match on
Pure
orImpure
.So a reasonable type signature might be:
fromFree :: Functor f => Free f a > Either a (Free1 f a)
but I am having problems writing this.
fromFree :: Free f a > Either a (Free1 f a) fromFree (Pure x) = Left x  easy fromFree (Impure x) = Right ??  a bit harder
It looks like the main problem is that we need to decide whether or not to use the
Done
or theMore
constructor without ever "running" the f. We need a:f (Free f a) > Free1 f a
which sounds like it might be troublesome for functors were you can't "get out", like
IO
.So, this sounds impossible, unless I'm missing something.
There's another encoding that I've tried:
data Free1 f a = Free1 (f (Free f a))
this does lets us define
fromFree
, and it borrows from theNonEmpty
construction (data NonEmpty a = a : [a]
). And I was able to use this approach when defining the "freeApply
", which was nice. This does let us writetoFree
,fromFree
,liftFree1
, and aBind
instances. However, I can't seem to writerunFree1
:runFree1 :: Bind g => (forall x. f x > g x) > f (Free f a) > g a
as soon as I do anything, I seem to require
return :: a > g a
, but we don't have this for allBind g
(I found a possible version that typechecks, but it performs the effects twice and so is not a proper bind homomorphism)So, while this method gives us
fromFree
, I can't seem to find a way to writerunFree1
, which is the very thing that gives it "freeBind
" capabilities.Of these two methods, either we:
 Have an actual free
Bind
withrunFree1
, but it is imcompatible withFree
in that you can't "match" aFree
into either aFree1
, or a pure value.  Have a type that is compatible with
Free
(maybe a "nonemptyFree
"), but is not actually a freeBind
(norunFree1
), and defeats the whole purpose.
From this I can make one of two conclusions:
 There is some way to make a free Bind
Free1
that is compatible withFree
, but I have not been able to figure it out yet  Fundamentally, we cannot have a free
Bind
that is compatible withFree
. This seems to contradict my intuition (we can always immediately decide if aFree
is pure or impure, so we should also be able to immediately distinguish between pure (zero effects) orFree1
), but maybe there is a deeper reason that I am missing out on?
Which of these is the case? If #1, what is way, and if #2, what is the deeper reason? :)
Thank you in advance!
Edit To dispel my uncertainty about whether or not I was working with a "true Free Bind", I started looking at one that was truly a Free Bind by definition:
newtype Free1 f a = Free1 { runFree1 :: forall g. Bind g => (forall x. f x > g x) > g a }
And I can't seem to be able to write
fromFree
for this one, either. In the end I seem to need ag (Either a (Free1 a)) > g a
.If I can't write
fromFree
for this, then it stands to reason that I can't writefromFree
for any implementation of the free bind, since all implementations are isomorphic to this one.Is there a way to write
fromFree
for this one, even? Or is it all impossible :'( It all worked so well forAlt
/Plus
andApply
/Applicative
.  The

Are free monads just monads with interfaces?
I've been reading some materials on free monads and I don't really think I'm much closer to implementation but I think I am closer to understanding what they are!
Given a lot of the above resources, what I understand is that free monads "free" the "monad" (which is a data type) from the "computational" work. In other words free monads provide the interface for things like
join
andmap
which the client will implement themselves? 
Confuse about free monad lifting and interpreter, example of binary tree dsl implement
i'm following the article stackless scala with free monads, and try to write my own code.
the function and common data type always confused me while lifting
sealed trait Free[F[_], A] { import Free._ def map[B](f: A => B): Free[F, B] = flatMap(f andThen (Done(_))) def flatMap[B](f: A => Free[F, B]): Free[F, B] = FlatMapped(this, f) /** flatMap 别名 */ final def >>=[B](f: A => Free[F, B]): Free[F, B] = this flatMap f final def fold[B](r: A => B, s: F[Free[F, A]] => B)(implicit F: Functor[F]): B = resume.fold(s, r) final def go(f: F[Free[F, A]] => Free[F, A])(implicit F: Functor[F]): A = { @tailrec def loop(t: Free[F, A]): A = t.resume match { case Left(s) => loop(f(s)) case Right(r) => r } loop(this) } @tailrec final def resume(implicit F: Functor[F]): Either[F[Free[F, A]], A] = this match { case Done(a) => Right(a) case Suspend(s) => Left(F.map(s)(Done(_))) case FlatMapped(sub, f) => sub match { case Done(a) => f(a).resume case Suspend(s) => Left(F.map(s)(f)) case FlatMapped(d, g) => d.flatMap(dd => g(dd).flatMap(f)).resume } } } object Free { def point[F[_], A](value: A): Free[F, A] = Done[F, A](value) def liftF[F[_], A](value: F[A]): Free[F, A] = Suspend(value) implicit val f0Functor: Functor[Function0] = new Functor[Function0] { override def map[A, B](a: () => A)(f: A => B): () => B = () => f(a()) } final case class Done[F[_], A](a: A) extends Free[F, A] final case class Suspend[F[_], A](s: F[A]) extends Free[F, A] final case class FlatMapped[F[_], E, A](a: Free[F, E], f: E => Free[F, A]) extends Free[F, A] }
here is my own dsl about binary tree
trait BTree[T] case class L[T](v: T) extends BTree[T] case class B[T](left: BTree[T], right: BTree[T]) extends BTree[T] trait BTreeFunctor[A] final case class BTDeepMapping[A](value: A) extends BTreeFunctor[A] type TreeDsl[A] = Free[BTreeFunctor, A] def lift[T](a: T): TreeDsl[T] = Free.liftF(BTDeepMapping[T](a)) implicit val treeDslFunctor: Functor[BTreeFunctor] = new Functor[BTreeFunctor] { override def map[C, D](a: BTreeFunctor[C])(f: C => D): BTreeFunctor[D] = { a match { case BTDeepMapping(v) => BTDeepMapping(f(v)) } } } def treeMap[A, B](treeDsl: TreeDsl[A => B], tree: BTree[A]): BTree[B] = treeDsl.resume.fold({ case BTDeepMapping(a) => treeMap(a, tree) }, _ => tree) def map[A, B](a: BTree[A])(f: A => B): BTree[B] = treeMap(lift(f), a)
and the demo code is:
val t: BTree[Int] = B(B(L(1), L(2)), L(3)) val expected = B(B(L(2), L(4)), L(6)) val actual = TreeFreeMonad.map(t)(_ * 2)
the
cats
library may much easier, likeobject Tree { implicit val treeFunctor: Functor[Tree] = new Functor[Tree] { override def map[A, B](fa: Tree[A])(f: A ⇒ B): Tree[B] = fa match { case Branch(l, r) ⇒ Branch(map(l)(f), map(r)(f)) case Leaf(v) ⇒ Leaf(f(v)) } } }
How can i fix the
map
implementation, am i misunderstood?