Monads/List monad

From Rosetta Code

Demonstrate in your programming language the following:

  1. Construct a List Monad by writing the 'bind' function and the 'unit' (sometimes known as 'return') function for that Monad (or just use what the language already has implemented)
  2. Make two functions, each which take a number and return a monadic number, e.g. Int -> List Int and Int -> List String
  3. Compose the two functions with bind


AppleScript[edit]

Translation of: JavaScript

We can use a list monad in AppleScript to express set comprehension for the Pythagorean triples, but the lack of nestable first class (and anonymous) functions means that the closure can only be achieved using script objects, which makes the idiom rather less direct and transparent. AppleScript is creaking at the seams here.

-- MONADIC FUNCTIONS (for list monad) ------------------------------------------
 
-- Monadic bind for lists is simply ConcatMap
-- which applies a function f directly to each value in the list,
-- and returns the set of results as a concat-flattened list
 
-- bind :: (a -> [b]) -> [a] -> [b]
on bind(f, xs)
-- concat :: a -> a -> [a]
script concat
on |λ|(a, b)
a & b
end |λ|
end script
 
foldl(concat, {}, map(f, xs))
end bind
 
-- Monadic return/unit/inject for lists: just wraps a value in a list
-- a -> [a]
on unit(a)
[a]
end unit
 
-- TEST ------------------------------------------------------------------------
on run
-- Pythagorean triples drawn from integers in the range [1..n]
-- {(x, y, z) | x <- [1..n], y <- [x+1..n], z <- [y+1..n], (x^2 + y^2 = z^2)}
 
pythagoreanTriples(25)
 
--> {{3, 4, 5}, {5, 12, 13}, {6, 8, 10}, {7, 24, 25}, {8, 15, 17},
-- {9, 12, 15}, {12, 16, 20}, {15, 20, 25}}
 
end run
 
-- pythagoreanTriples :: Int -> [(Int, Int, Int)]
on pythagoreanTriples(maxInteger)
script X
on |λ|(X)
script Y
on |λ|(Y)
script Z
on |λ|(Z)
if X * X + Y * Y = Z * Z then
unit([X, Y, Z])
else
[]
end if
end |λ|
end script
 
bind(Z, enumFromTo(1 + Y, maxInteger))
end |λ|
end script
 
bind(Y, enumFromTo(1 + X, maxInteger))
end |λ|
end script
 
bind(X, enumFromTo(1, maxInteger))
 
end pythagoreanTriples
 
 
-- GENERIC FUNCTIONS ---------------------------------------------------------
 
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
 
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
 
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
Output:
{{3, 4, 5}, {5, 12, 13}, {6, 8, 10}, {7, 24, 25}, {8, 15, 17}, {9, 12, 15}, {12, 16, 20}, {15, 20, 25}}

Clojure[edit]

 
(defn bind [coll f] (apply vector (mapcat f coll)))
(defn unit [val] (vector val))
 
(defn doubler [n] [(* 2 n)]) ; takes a number and returns a List number
(def vecstr (comp vector str)) ; takes a number and returns a List string
 
(bind (bind (vector 3 4 5) doubler) vecstr) ; evaluates to ["6" "8" "10"]
(-> [3 4 5]
(bind doubler)
(bind vecstr)) ; also evaluates to ["6" "8" "10"]
 

EchoLisp[edit]

Our monadic lists will take the form (List a b c ...), ie raw lists prefixed by the List symbol.

 
;; -> and ->> are the pipeline operators
;; (-> x f g h) = (h (g ( f x)))
;; (->> x f (g a) h) = (h (g a ( f x)))
 
(define (List.unit elem) (append '(List) elem))
(define (List.bind xs f) (List.unit (->> xs rest (map f) (map rest) (apply append))))
(define (List.lift f) (lambda(elem) (List.unit (f elem))))
 
(define List.square (List.lift (lambda(x) (* x x))))
(define List.cube (List.lift (lambda(x) (* x x x))))
(define List.tostr (List.lift number->string))
 
;; composition
 
(-> '(List 1 -2 3 -5) (List.bind List.cube) (List.bind List.tostr))
(List "1" "-8" "27" "-125")
;; or
(-> '(1 -2 3 -5) List.unit (List.bind List.cube) (List.bind List.tostr))
(List "1" "-8" "27" "-125")
 

Haskell[edit]

Haskell has the built-in Monad type class, and the built-in list type already conforms to the Monad type class.

main = print $ [3,4,5] >>= (return . (+1)) >>= (return . (*2)) -- prints [8,10,12]

Or, written using do notation:

main = print $ do x <- [3,4,5]
y <- return (x+1)
z <- return (y*2)
return z

Or alternately:

main = print $ do x <- [3,4,5]
let y = x+1
let z = y*2
return z

Using the list monad to express set comprehension for Pythagorean triples:

pythagoreanTriples :: Integer -> [(Integer, Integer, Integer)]
pythagoreanTriples n =
[1 .. n] >>= (\x ->
[x+1 .. n] >>= (\y ->
[y+1 .. n] >>= (\z ->
if x^2 + y^2 == z^2 then return (x,y,z) else [])))
 
main = print $ pythagoreanTriples 25
Output:
[(3,4,5),(5,12,13),(6,8,10),(7,24,25),(8,15,17),(9,12,15),(12,16,20),(15,20,25)]

Which can be written using do notation:

pythagoreanTriples :: Integer -> [(Integer, Integer, Integer)]
pythagoreanTriples n = do x <- [1 .. n]
y <- [x+1 .. n]
z <- [y+1 .. n]
if x^2 + y^2 == z^2 then return (x,y,z) else []

Or directly as a list comprehension:

pythagoreanTriples :: Integer -> [(Integer, Integer, Integer)]
pythagoreanTriples n = [(x,y,z) | x <- [1 .. n], y <- [x+1 .. n], z <- [y+1 .. n], x^2 + y^2 == z^2]

J[edit]

Note that J documentation mentions "monad" but that is an older (much older) use of the term from what is intended here. J documentation uses "box" <to describe the operation mentioned here.

That said, here is an implementation which might be adequate for the current task description:

bind=: S:0
unit=: boxopen
 
m_num=: unit
m_str=: unit@":

Task example:

   m_str bind m_num 5
┌─┐
5
└─┘

JavaScript[edit]

 
Array.prototype.bind = function (func) {
return this.map(func).reduce(function (acc, a) { return acc.concat(a); });
}
 
Array.unit = function (elem) {
return [elem];
}
 
Array.lift = function (func) {
return function (elem) { return Array.unit(func(elem)); };
}
 
inc = function (n) { return n + 1; }
doub = function (n) { return 2 * n; }
listy_inc = Array.lift(inc);
listy_doub = Array.lift(doub);
 
[3,4,5].bind(listy_inc).bind(listy_doub); // [8, 10, 12]
 


ES5 Example: Using the list monad to express set comprehension

(function (n) {
 
// ENCODING A SET COMPREHENSION IN TERMS OF A LIST MONAD
 
// Pythagorean triples drawn from integers in the range [1..25]
 
 
// Each range of integers here represents the set of possible values for the variable.
// Where the test returns true for a particular [x, y, z] triple, we return that triple
// to the expected data type, wrapping it using the unit or return function;
 
// Where the test returns false, we return the empty list, which vanishes from the
// results set under concatenation, giving us a convenient encoding of filtering.
 
// {(x, y, z) | x <- [1..n], y <- [x+1..n], z <- [y+1..n], (x^2 + y^2 = z^2)}
 
return bind(rng(1, n), function (x) {
return bind(rng(1 + x, n), function (y) {
return bind(rng(1 + y, n), function (z) {
 
return (x * x + y * y === z * z) ? unit([x, y, z]) : [];
 
})})});
 
 
// Monadic return/unit/inject for lists just wraps a value in a list
// a -> [a]
function unit(a) {
return [a];
}
 
// Bind for lists is simply ConcatMap
// which applies a function f directly to each value in the list,
// and returns the set of results as a concat-flattened list
// [a] -> (a -> [b]) -> [b]
function bind(xs, f) {
return [].concat.apply([], xs.map(f));
}
 
 
 
// we will need some ranges of integers, each expressing a range of possible values
// [m..n]
function rng(m, n) {
return Array.apply(null, Array(n - m + 1))
.map(function (x, i) {
return m + i;
});
}
 
})(25);
Output:
[[3, 4, 5], [5, 12, 13], [6, 8, 10], [7, 24, 25], [8, 15, 17], [9, 12, 15], [12, 16, 20], [15, 20, 25]]

Ruby[edit]

 
class Array
def bind(f)
flat_map(&f)
end
def self.unit(*args)
args
end
# implementing lift is optional, but is a great helper method for turning
# ordinary funcitons into monadic versions of them.
def self.lift(f)
-> e { self.unit(f[e]) }
end
end
 
inc = -> n { n + 1 }
str = -> n { n.to_s }
listy_inc = Array.lift(inc)
listy_str = Array.lift(str)
 
Array.unit(3,4,5).bind(listy_inc).bind(listy_str) #=> ["4", "5", "6"]
 
# Note that listy_inc and listy_str cannot be composed directly,
# as they don't have compatible type signature.
# Due to duck typing (Ruby will happily turn arrays into strings),
# in order to show this, a new function will have to be used:
 
doub = -> n { 2*n }
listy_doub = Array.lift(doub)
[3,4,5].bind(listy_inc).bind(listy_doub) #=> [8, 10, 12]
 
# Direct composition will cause a TypeError, as Ruby cannot evaluate 2*[4, 5, 6]
# Using bind with the composition is *supposed* to fail, no matter the programming language.
comp = -> f, g {-> x {f[g[x]]}}
[3,4,5].bind(comp[listy_doub, listy_inc]) #=> TypeError: Array can't be coerced into Fixnum
 
# Composition needs to be defined in terms of bind
class Array
def bind_comp(f, g)
bind(g).bind(f)
end
end
 
[3,4,5].bind_comp(listy_doub, listy_inc) #=> [8, 10, 12]
 

zkl[edit]

While I'm unsure of the utility of Monads in a dynamic type-less language, it can be done.

Translation of: Ruby

Here we create a class to do Monad like things. Unlike Ruby, we can't augment the baked in List/Array object so this more verbose. Also unlike Ruby, we can directly compose as we are applying the composition to each element (vs the list-as-object).

class MList{
fcn init(xs){ var list=vm.arglist }
fcn bind(f) { list=list.apply(f); self }
fcn toString{ list.toString() }
}
inc:=Op("+",1);  // '+(1)
str:="toString";
MList(3,4,5).bind(inc).bind(str).println(" == (4,5,6)");
 
doub:=Op("*",2);
MList(3,4,5).bind(inc).bind(doub).println(" == (8,10,12)");
 
comp:=Utils.Helpers.fcomp; // comp(f,g) == f.g == f(g(x))
MList(3,4,5).bind(comp(doub,inc)).println(" == (8,10,12)");
Output:
L("4","5","6") == (4,5,6)
L(8,10,12) == (8,10,12)
L(8,10,12) == (8,10,12)