foldM about cats HOT 28 CLOSED

I'd like to work on this one.

from cats.

Fine! Github doesn't allows assign issues to external people. So we keep in mind that you are working on this. Thanks!

from cats.

Cool. Working on it here.

from cats.

Looks like I don't have the proper time to commit to this right now.

Here's what I came up with so far:

(defn foldseq
  [f val mvs]
  {:pre [(not-empty mvs)]}
  (let [ctx (get-current-context (first mvs))]
    (with-monad ctx
      (reduce (fn [mz mv]
                (mlet [z mz
                       v mv]
                  (f z v)))
              (return val)
              mvs))))

Might be obsoleted by #62.

from cats.

Thanks for your time @yurrriq, looks like a generic foldlM and foldrM can be implemented in terms of Foldable's foldl and foldr.

from cats.

I figured. Can't wait to play around with it!

from cats.

This is already implemented in 9e812ec

Thank you very much for the initial implementation.

from cats.

👍

from cats.

I have reopened this issue because the foldM finally is not merged into master.
We should research on how to implement correctly the foldM.

Additional notes: http://members.chello.nl/hjgtuyl/tourdemonad.html#foldM

from cats.

I've got another implementation almost ready. It takes a context as the first argument. Without static typing of the fold function, that might be the only way..

from cats.

Yes, since the monadic type is what the reducing function returns. Looking forward to see what you've come up with @yurrriq!

from cats.

Edit: This code is at yurrriq/cats@foldM.

Second Draft

It's basically a literal translation of the Haskell:

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

(defn foldm [ctx f z xs]
  (letfn [(foldm' [z' xs']
            (if (empty? xs')
              (return ctx z')
              (let [[h & t] xs']
                (>>= (f z' h) (fn [z''] (foldm' z'' t))))))]
    (foldm' z xs)))

Example

Based on the example at the link @niwinz posted.

(require '[cats.monad.maybe :as maybe])

(defn- m-div [x y]
  (if (zero? y)
    (maybe/nothing)
    (maybe/just (/ x y))))

(foldm maybe/maybe-monad m-div 1 [1 2 3])
;; => #<Just 1/6>

(foldm maybe/maybe-monad m-div 1 [1 2 0])
;; => #<Nothing>

from cats.

Another approach would be to use custom metadata on the folding function to store the context of the return value and then pass it as a var, e.g.

(defn- m-div
  {:cats.core/context maybe/maybe-monad}
  [x y]
  (if (zero? y)
    (maybe/nothing)
    (maybe/just (/ x y))))

(defn foldm*
  [f z xs]
  {:pre [(->> (get (meta f) ::context) (satisfies? p/Monad))]}
  (let [ctx (get (meta f) ::context)]
    (letfn [(foldm' [z' xs']
              (if (empty? xs')
                (return ctx z')
                (let [[h & t] xs']
                  (>>= (f z' h) (fn [z''] (foldm' z'' t))))))]
      (foldm' z xs))))


(foldm* #'m-div 1 [1 2 3])
;; => #<Just 1/6>

A good example of a library that uses similar metadata management is dire.

But having to pass vars around is less than ideal. Is there a way to attach metadata to anonymous functions? We could perhaps use with-meta to attach :cats.core/context to anonymous functions.

Edit: It works!

(foldm*
 (with-meta
   (fn [x y]
     (if (zero? y)
       (maybe/nothing)
       (maybe/just (/ x y))))
   {:cats.core/context maybe/maybe-monad})
 1
 [6 5 4 3 2])
;; => #<Just 1/720>

from cats.

It's pretty trivial to write a macro to wrap anonymous functions in a with-meta form.

(defmacro mfn [ctx & body]
  `(with-meta (fn ~@body) {:cats.core/context ~ctx}))

(foldm*
 (mfn maybe/maybe-monad
   [x y]
   (if (odd? y)
     (maybe/nothing)
     (maybe/just (* x y))))
 1
 (repeat 8 2))
;; => #<Just 256>

But what could be even better (or maybe both would be good) is to add a third arity to lift-m that wraps a call to the two argument lift-m in a with-meta form.

Sorry for lengthy thought dumps..

from cats.

Sorry for lengthy thought dumps..

No problem, it's great food for thought! However I think the metadata approach can be moved to separate
conversation about context management, the current approach is not very convenient for things like monad
transformers and we may be able to improve it using metadata. Feel free to open an issue to start the
discussion!

More succinctly without the currying:

(defn foldm [ctx f z xs]
  (letfn [(foldm' [z' xs']
            (if (empty? xs')
              (return ctx z')
              (let [[h & t] xs']
                (>>= (f z' h) (fn [z''] (foldm' z'' t))))))]
    (foldm' z xs)))

Looks good! We added a currying macro recently that can be used together with foldm in case you want currying.

We may want do to the ctx argument optional, having 3 arity when we know xs is not empty and >>= will
derive and set it. This way, the call to return in foldm' can be left as (return z').

(defn foldm
  ([f z xs]
    (letfn [(foldm' [z' xs']
              (if (empty? xs')
                (return z')
                (let [[h & t] xs']
                  (>>= (f z' h) (fn [z''] (foldm' z'' t))))))]
      (foldm' z xs)))
  ([ctx f z xs]
    ;; ...
    ))

In cases when xs is not empty the context will be set by the first >>= and in places like mlet the
context is already set.

(require '[cats.monad.maybe :as maybe])

(defn- m-div [x y]
  (if (zero? y)
    (maybe/nothing)
    (maybe/just (/ x y))))

(foldm m-div 1 [1 2 3])
;; => #<Just 1/6>

;; we may want to provide a friendlier error message here
(foldm m-div 1 [])
;; IllegalArgumentException You are using return/pure/mzero function without context.  cats.context/get-current (context.cljc:62

(foldm maybe/maybe-monad m-div 1 [])
;; => #<Just 1>

(mlet [x (maybe/just 1)
       y (foldm m-div 1 [1 2 3])]
  (return (+ x y)))
;; => #<Just 7/6>

from cats.

I love that!

With the ternary implementation I just added to my branch:

(let [f m-div, z 1, xs [1 2 3]]
  (= (foldm maybe/maybe-monad f z xs)
     (foldm f z xs)))
;; => true

(foldm m-div 1 [])
;; => AssertionError Assert failed: (seq xs)  cats.core/foldm

(foldm maybe/maybe-monad m-div 1 [])
;; => #<Just 1>

from cats.

Looks awesome.

Maybe the precondition is a bit too strict. For example I may be using foldm wrapped in a with-context macro that sets the context and expect that if given an empty sequence foldm wi'll be able to use return because context is set.

(with-context maybe-monad
  (foldm m-div 1 []))
;; => #<Just 1>

from cats.

Would something like (or *context* (seq xs)) (or (seq xs) (get-current-context)) work?

from cats.

I think so. Note that *context* now lives in the cats.context namespace.

from cats.

Noted. It doesn't quite work. I'm experimenting now.

from cats.

(defn foldm
  ([f z xs]
   (if (empty? xs)
     (return (get-current-context) z)
     (let [[h & t] xs]
       (mlet [z' (f z h)]
         (if (empty? t)
           (return z')
           (foldm f z' t))))))
  ([ctx f z xs]
   (if (empty? xs)
     (return ctx z)
     (foldm f z xs))))

(with-context maybe-monad
  (foldm m-div 1 []))
;; => #<Just 1>

(foldm m-div 1 [])
;; IllegalArgumentException You are using return/pure/mzero function without context.  cats.context/get-current (context.cljc:62

(foldm maybe-monad m-div 1 [])
;; => #<Just 1>

A perhaps undesirable side effect, however, is this:

(with-context either-monad
  (foldm m-div 1 [1 2 3]))
;; => #<Just 1>

from cats.

Maybe a precondition is not the best choice here anymore, since this latest idea ends up calling (seq xs) and possibly (get-current-context) twice.

from cats.

Maybe a precondition is not the best choice here anymore, since this latest idea ends up calling (seq xs) and possibly (get-current-context) twice.

Let's get rid of it then, no problem.

@niwinz what do you think about the current proposal?

from cats.

As quick review seems ok for me!

@yurrriq feel free open the pr for the final review and merge!

And thank you very much to both!

from cats.

👍 I'm AFK for the next couple days but I should be able to clean up, write tests and make a PR on Sunday (CDT).

from cats.

No hurries, thanks for your time!

from cats.

Sounds good. PS I'm hoping to port cats to LFE in the reasonably near future, using flavors.

from cats.

I think this can be closed now. 😄

from cats.