-
Notifications
You must be signed in to change notification settings - Fork 66
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
foldM #55
Comments
I'd like to work on this one. |
Fine! Github doesn't allows assign issues to external people. So we keep in mind that you are working on this. Thanks! |
Cool. Working on it here. |
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. |
Thanks for your time @yurrriq, looks like a generic foldlM and foldrM can be implemented in terms of Foldable's foldl and foldr. |
I figured. Can't wait to play around with it! |
This is already implemented in 9e812ec Thank you very much for the initial implementation. |
👍 |
I have reopened this issue because the foldM finally is not merged into master. Additional notes: http://members.chello.nl/hjgtuyl/tourdemonad.html#foldM |
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.. |
Yes, since the monadic type is what the reducing function returns. Looking forward to see what you've come up with @yurrriq! |
Edit: This code is at yurrriq/cats@foldM. Second DraftIt'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))) ExampleBased 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> |
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. 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> |
It's pretty trivial to write a macro to wrap anonymous functions in a (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 Sorry for lengthy thought dumps.. |
No problem, it's great food for thought! However I think the metadata approach can be moved to separate
(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 We may want do to the (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 (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> |
When xs is not empty, we don't need the explicit context. See @dialelo's comment on funcool#55
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> |
Looks awesome. Maybe the precondition is a bit too strict. For example I may be using (with-context maybe-monad
(foldm m-div 1 []))
;; => #<Just 1> |
Would something like |
I think so. Note that |
Noted. It doesn't quite work. I'm experimenting now. |
(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> |
Maybe a precondition is not the best choice here anymore, since this latest idea ends up calling |
- Dropped precondition - Fixed and reordered logic funcool#55
Let's get rid of it then, no problem. @niwinz what do you think about the current proposal? |
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! |
👍 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). |
No hurries, thanks for your time! |
I think this can be closed now. 😄 |
When xs is not empty, we don't need the explicit context. See @dialelo's comment on funcool/cats#55
- Dropped precondition - Fixed and reordered logic funcool/cats#55
No description provided.
The text was updated successfully, but these errors were encountered: