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

How would I find the distance between two elements in a list?
I have to find the distance between first appearance of two elements in a list. The program we are using is Haskell. I've been online for HOURS trying to look for help on how to start or direction to solve it. Please help!
This is how we are defining it:
gap :: (Eq a) => a > a > [a] > Maybe Int
Here are some examples:
> gap 3 8 [1..10] Just 5 > gap 8 3 [1..10] Nothing > gap 'h' 'l' "hello" Just 2 > gap 'h' 'z' "hello" Nothing

Haskell alternative for Doublylinkedlist coupled with Hashtable pattern
There's a useful pattern in imperative programming, namely, a doublylinkedlist coupled with a hashtable for constant time lookup in the linked list.
One application of this pattern is in LRU cache. The head of the doublylinkedlist will contain the least recently used entry in the cache and the last element in the doublylinkedlist will contain the most recently used entry. The keys in the hashtable are keys of the entries and the values are pointers to nodes in the linkedlist corresponding to the key/entry. When an entry is queried in the cache, hashtable will be used to point to its node in the linkedlist and then the node will be removed from its current location in the linkedlist and be placed at the end of the linkedlist making it the mostrecentlyused entry. For eviction, we simply remove entries from the head of the linkedlist as they are the least recently used ones. Both lookup and eviction operations will take constant time.
I can think of implementing this in Haskell using two TreeMaps and I know that the time complexity will be O(log n). But I am a little uncomfortable as the constant factor in the time complexity seems a little high. Specifically, to perform a lookup, first I need to check if the entry exists and save its value, then I need to first delete it from the LRU map and reinsert it with a new key. This means that each lookup will result in a roottonode traversal three times.
Is there a better way of doing this in Haskell?

Does the usage of Parser make sense?
I have the following text and would like to transform into a data structure.
The text is:
pcpaction:MESSAGE\npcpchannel:apc\:///\npcpbodytype:text\nPUBLIC:THISPK\nTOPIC:SEND\n\nHello Foo
I would like to know, if it makes sense to use Parser for it. To be honestly, I can not see the sense to use
Parser
in this case, because the structure is not inBNF
like for exampleJSON
and it is not recursively enumerable.When does it make sense to transform a text with
Parser
into a data structure?Update
I forget to mention the text above is based on the following description, that is written here https://blogs.sap.com/2015/07/27/specificationofthepushchannelprotocolpcp/.
It looks like, it is based on a grammar.

How to detect a loop in a hierarchy of javascript elements
I have a list of elements, each has an ID and a parent ID. What I want to do is detect when there is a loop in this 'hierarchy', and show which ID starts the loop.
list = [ { id: '1', parent: '2' }, { id: '2', parent: '3' }, { id: '3', parent: '4' }, { //This id is causing the loop id: '4', parent: '1' } ]
I have tried this to build the tree, which works when there's no loop, but does not work with a loop:
function treeify(list, idAttr, parentAttr, childrenAttr) { if (!idAttr) idAttr = 'id'; if (!parentAttr) parentAttr = 'parent'; if (!childrenAttr) childrenAttr = 'children'; var treeList = []; var lookup = {}; list.forEach(function(obj) { lookup[obj[idAttr]] = obj; obj[childrenAttr] = []; }); list.forEach(function(obj) { if (obj[parentAttr] != null) { lookup[obj[parentAttr]][childrenAttr].push(obj); } else { treeList.push(obj); } }); return treeList; };
I also cannot detect when there is a loop.
I'd like to return the ID of the element that caused the loop to allow me to fix the data behind it.

Optimal solution for tree traversal and summing node values on condition
Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can be random number).
What i want to do is traverse tree and for each node i want to sum values from all descendant nodes except descendants with lower rank and all nodes under them (irrespective of rank). Tree does not have any special properties as every node can have <0, Integer.MAX_VALUE> of children. There are no rules applied on relations between parent and children regarding rank or value.
My naive solution is to recursively traverse subtree for each node and stop recursion as soon as i find node with lower rank, summing values on my way back to root of subtree. However this feels to me like suboptimal solution (in worst case  that is each node has only one descendant  its basically linked list and ranks are sorted ascending to the root this solution would be O(n^2)).
It is possible to have sums for all nodes settled after one traversal?
Edit: Solution, slightly better as my naive approach could be for every node visited propagate its value recursively back to the root while keeping minimum rank of visited nodes (during back to root traversal). Then adding value only to nodes that have lower than minimal rank.

How to optimize building a tree from a list of the node paths?
Suppose I am writing a function
fromPaths(paths: List[String]): Node
to build a tree from a few node paths like this:case class Node(value: String, children: List[Node]) val paths = List("a/b/x", "a/b/y", "a/c", "a/c/d") fromPaths(paths) // Node("a", List(Node("b", List(Node("x"), Node("y"))), Node("c", List(Node("d")))))
I can write a function
addNode(root: Node, path: String): Node
and then justfold
it over the list. However it looks suboptimal since we traverse the tree fromroot
tonode
for each "path" inpaths
.How would you optimize
fromPaths
for the overall number of traversed nodes ? 
Why does Haskell presume the returned monad type is the same type that is passed as an argument?
Why does this code compile?
sequence_mine :: Monad m => [m a] > m [a] sequence_mine [] = return [] sequence_mine (elt:l) = do e < elt sl < sequence l return (e:sl)
Note I intentionally commented out the type declaration here. But the code still compiles and seems to work as expected, even without the type declaration  and this is what surprises me.
To my understanding, ambiguity should arise on this line:
return (e:sl)
The reason is that Haskell shouldn't know which type of monad we are returning. Why does it have to be the same type that we are accepting?
To clarify more. To my understanding, if I don't explicitely put the type declaration analogous to the one I commented out, Haskell should deduce this function has a typing like this:
sequence_mine :: (Monad m1, Monad m2) => [m1 a] > m2 [a]
Unless I explicitely unify
m1
andm2
by calling them bothm
, there is no reason for Haskell to believe they both refer to the same type! I would suppose.Yet that is not the case. What am I missing here?

Haskell error Couldn't match expected type `IO b0' with actual type `Bool'
I'm getting the "Couldn't match expected type
IO b0' with actual type
Bool'" error in my code when trying to return a boolean from a function which calls a Monad function.I realize that the way I'm doing it is completely wrong but I'm not sure what the correct way is, if someone could help me that would appreciated.
getFiles :: [Day] > [FilePath] getFiles days = do filter (isFileOk) (map (getOrderPath) days) isFileOk :: FilePath > Bool isFileOk file = do exists < doesFileExist file if exists then True else False
Full Error:
* Couldn't match expected type `IO b0' with actual type `Bool' * In a stmt of a 'do' block: True In the expression: do exists < doesFileExist file True In an equation for `isFileOk': isFileOk file = do exists < doesFileExist file True
 29  True

Checking that Aplicative realization correct for Cont
I'm try to understand Cont in Haskell, so I implement
Functor
,Applicative
andMonad
for this.I'm define
Cont
asnewtype Cont r a = Cont {runCont :: (a > r) > r}
Now I'm try to implemente
<*>
.I'm suppose that realization is
Cont func <*> Cont value = (\r > value (\a > func (\c > r (c a))))
but in MTL
Cont func <*> Cont value = Cont (\r > func (\f > value (\ a > r (f a) )))
found that realization.Now my question is: how can I provide that my realization is correct? I'm think to proof
Applicative
laws, but for me it's not obviously how do this. 
How can I use functors or applicatives to rewrite this Haskell function over lists of tuples
Is there a nicer way to write the following function
fs'
with functors or applicatives?fncnB = (* 2) fncnA = (* 3) fs' fs = zip (map (fncnA . fst) fs) $ map (fncnB . snd) fs
I see from this question that I could rely on the functor instance of lists to map a single function acting over both elements of each tuple, or e.g. on the applicative instance of tuples to apply functions to just the secondhalf of a twotuple, but I'm curious how functors and applicatives fit into the picture of operating over lists of multicomponent data types.

How to compose functions with applicative effects for Validation in the Cats in Scala
Here is an example from the Scala with Cats book:
object Ex { import cats.data.Validated type FormData = Map[String, String] type FailFast[A] = Either[List[String], A] def getValue(name: String)(data: FormData): FailFast[String] = data.get(name).toRight(List(s"$name field not specified")) type NumFmtExn = NumberFormatException import cats.syntax.either._ // for catchOnly def parseInt(name: String)(data: String): FailFast[Int] = Either.catchOnly[NumFmtExn](data.toInt).leftMap(_ => List(s"$name must be an integer")) def nonBlank(name: String)(data: String): FailFast[String] = Right(data).ensure(List(s"$name cannot be blank"))(_.nonEmpty) def nonNegative(name: String)(data: Int): FailFast[Int] = Right(data).ensure(List(s"$name must be nonnegative"))(_ >= 0) def readName(data: FormData): FailFast[String] = getValue("name")(data). flatMap(nonBlank("name")) def readAge(data: FormData): FailFast[Int] = getValue("age")(data). flatMap(nonBlank("age")). flatMap(parseInt("age")). flatMap(nonNegative("age")) case class User(name: String, age: Int) type FailSlow[A] = Validated[List[String], A] import cats.instances.list._ // for Semigroupal import cats.syntax.apply._ // for mapN def readUser(data: FormData): FailSlow[User] = ( readName(data).toValidated, readAge(data).toValidated ).mapN(User.apply)
Some notes: each primitive validation function:
nonBlank
,nonNegative
,getValue
returns so called FailFast type, which is monadic, not applicative.There are 2 functions
readName
andreadAge
, which use a composition of the previous ones, and also are FailFast by the nature.The
readUser
is on the contrary, fail slow. To achieve it results ofreadName
andreadAge
are converted to Validated and composed through so called "Syntax"Let's assume I have another function for validation, that accepts name and age, validated by
readName
andreadAge
. For intstance://fake implementation: def validBoth(name:String, age:Int):FailSlow[User] = Validated.valid[List[String], User](User(name,age))
How to compose
validBoth
withreadName
and readAge? With fail fast it is quite simple, cause I useforcomrehension
and have access to the results ofreadName
andreadAge
:for { n < readName... i < readAge... t < validBoth(n,i) } yield t
but how to get the same result for failslow?
EDIT probably it is not clear enough, with these function. Here is a real use case. There is a function, similar to readName/readAge that validates date in the similar way. I want to create a validation fucntion, that accepts 2 dates, to make sure that one date comes after another. Date comes from String. Here is an example, how it will look like for FailFast, which is not the best option in this context:
def oneAfterAnother(dateBefore:Date, dateAfter:Date): FailFast[Tuple2[Date,Date]] = Right((dateBefore, dateAfter)) .ensure(List(s"$dateAfter date cannot be before $dateBefore"))(t => t._1.before(t._2)) for { dateBefore < readDate... dateAfter < readDate... t < oneDateAfterAnother(dateBefore,dateAfter) } yield t
My purpose is to accumulate possible errors with dates in applicative way. In the book it is said, p. 157:
We can’t flatMap because Validated isn’t a monad. However, Cats does provide a standin for flatMap called andThen . The type signature of andThen is identical to that of flatMap, but it has a different name because it is not a lawful implementation with respect to the monad laws:
32.valid.andThen { a => 10.valid.map { b => a + b } }
Ok, I tried to reuse this solution, based on
andThen
, but the result had monadic, but not applicative effect:def oneDateAfterAnotherFailSlow(dateBefore:String, dateAfter:String) (map: Map[String, String])(format: SimpleDateFormat) : FailSlow[Tuple2[Date, Date]] = readDate(dateBefore)(map)(format).toValidated.andThen { before => readDate(dateAfter)(map)(format).toValidated.andThen { after => oneAfterAnother(before,after).toValidated } }

Interpreters for the Free Monad
I've been doing an exercise to try to implement a basic Calculator with Free Monad. As I understand the intention of the Free Monad and what I wanted to achieve is: write my program (math expression) once run it with different interpreters. Now i am not sure that I did the 100% idiomatic implementation at least because:
My program kinda needs to be parametrized on the generic type A which should match the interpreter context.
def program[A] = for { two < lit[A](2) four < lit[A](4) sum < add(two, four) } yield sum program[Int].foldMap(eval) shouldBe 6 program[String].foldMap(print) shouldBe "(2 + 4)" import cats.instances.option._ program[Option[Int]].foldMap(evalOpt) shouldBe Option(6)
The ADT/algebra and 'smart constructors'
trait Expression2[A] extends Product with Serializable case class Lit[A](a: Int) extends Expression2[A] case class Add[A](a: A, b: A) extends Expression2[A] case class Mult[A](a: A, b: A) extends Expression2[A] type ExprAlg[B] = Free[Expression2, B] def lit[A](a: Int): ExprAlg[A] = Free.liftF(Lit(a)) def add[A](a: A, b: A): ExprAlg[A] = Free.liftF(Add(a, b)) def mult[A](a: A, b: A): ExprAlg[A] = Free.liftF(Mult(a, b))
The math interpreter:
def eval: Expression2 ~> Id = new (Expression2 ~> Id) { override def apply[A](fa: Expression2[A]): Id[A] = eval(fa).asInstanceOf[A] def eval[A](expression2: Expression2[A]): Int = expression2 match { case Lit(n) => n case Add(a, b) => a.asInstanceOf[Int] + b.asInstanceOf[Int] case Mult(a, b) => a.asInstanceOf[Int] * b.asInstanceOf[Int] } }
The print interpreter:
def print: Expression2 ~> Id = new (Expression2 ~> Id) { override def apply[A](fa: Expression2[A]): Id[A] = eval(fa).asInstanceOf[A] def eval[A](expression2: Expression2[A]): String = expression2 match { case Lit(n) => n.toString case Add(a, b) => "(" + a.toString + " + " + b.toString + ")" case Mult(a, b) => "(" + a.toString + " * " + b.toString + ")" } }
The math in Option interpreter:
def evalOpt: Expression2 ~> Option = new (Expression2 ~> Option) { override def apply[A](fa: Expression2[A]): Option[A] = eval(fa).map{_.asInstanceOf[A]} def eval[A](expression2: Expression2[A]): Option[Int] = expression2 match { case Lit(n) => Option(n) case Add(a, b) => Option(a.asInstanceOf[Int] + b.asInstanceOf[Int]) case Mult(a, b) => Option(a.asInstanceOf[Int] * b.asInstanceOf[Int]) } }
Related to the Option interpreter, I would have expected that the a and b vars to be option, and in the string interpreter a and b to be strings because of my the ADT result type is A: Expression2[A].
I also tried instead of Lit[A](a: Int), to have Lit[A](a: A) but then it breaks down: i cannot pass different interpreters for the same expression when A is fixed to an Int in my program and I expect not to have to rewrite my program for different interpreters.

Zipping free monad transformers
The
streaming
package offers azipsWith
functionzipsWith :: (Monad m, Functor h) => (forall x y. f x > g y > h (x, y)) > Stream f m r > Stream g m r > Stream h m r
and a slightly more streamlined version,
zipsWith' :: Monad m => (forall x y p. (x > y > p) > f x > g y > h p) > Stream f m r > Stream g m r > Stream h m r
These can be adapted very easily to
FreeT
from thefree
package. But that package offers another version of the free monad transformer:newtype FT f m a = FT { runFT :: forall r. (a > m r) > (forall x. (x > m r) > f x > m r) > m r }
There is also a third (rather simple) formulation:
newtype FF f m a = FF { runFF :: forall n. Monad n => (forall x. f x > n x)  A natural transformation > (forall x. m x > n x)  A monad morphism > n a }
It is possible to convert back and forth between
FreeT
and eitherFT
orFF
, which offers an indirect way to implementzipsWith
and its relatives forFF
andFT
. But that seems quite unsatisfying. I seek a more direct solution.The problem seems related to the challenge of zipping lists using folds. This has been addressed in a paper, Coroutining Folds with Hyperfunctions, by Launchbury et al, as well as a blog post by Donnacha Kidney. Neither of these are terribly simple, and I have no idea how they might be adapted to the
FT
orFF
contexts.
As I've looked into this problem, I've realized that
streaming
should really offer some more powerful versions. The simplest would be something likezipsWith'' :: Monad m => (forall x y p. (x > y > p) > f x > g y > h p) > Stream f m r > Stream g m s > Stream h m (Either r s)
but a more powerful option would include the remainder:
zipsWithRemains :: Monad m => (forall x y p. (x > y > p) > f x > g y > h p) > Stream f m r > Stream g m s > Stream h m (Either (r, Stream g m s) (f (Stream f m r), s))
I would guess that
zipsWith''
would be no harder thanzipsWith'
, but thatzipsWithRemains
might be a bigger challenge in this context, since the remainder will presumably have to be reconstituted somehow.