7
\$\begingroup\$

I'm trying to write code to solve water pouring problem in Clojure. The following code is strongly influenced by Martin Odersky's solution lectured in his coursera course, Functional Programming Principle in Scala. He first created a class Pouring with parameter capacity, which is accessible everywhere in the class. Though he made the best use of case class in his solution, I just used plain clojure map to represent the moves.

I tried to solve the problem in the same way, and end up with the following code:

(ns pouring)

(declare capacity init-state)

(defn empty [state glass]
  (assoc state glass 0))

(defn fill [state glass]
  (assoc state glass (capacity glass)))

(defn pour [state [from to]]
  (let [amt (min (state from) (- (capacity to) (state to)))]
    (-> state
        (assoc from (- (state from) amt))
        (assoc to (+ (state to) amt)))))

(defn change [state move]
  (if state
    (cond (:empty move) (empty state (:empty move))
          (:fill move) (fill state (:fill move))
          (:pour move) (pour state (:pour move)))
    (change init-state move)))

(defn moves [capacity]
  (let [glasses (range (count capacity))]
    (lazy-cat
     (map (fn [g] {:empty g}) glasses)
     (map (fn [g] {:fill g}) glasses)
     (for [from glasses, to glasses :when (not= from to)]
       {:pour [from to]}))))

(defn extend-path [path move]
  {:history (conj (:history path) move)
   :end-state (change (:end-state path) move)})

(defn extend
  ([paths explored]
   (if-let [more (for [path paths
                       next-path (map #(extend-path path %) (moves capacity))
                       :when (not (contains? explored (:end-state next-path)))]
                   next-path)]
     (lazy-cat paths (extend more (conj explored (map #(:end-state %) more))))))
  ([] (extend #{{:history [], :end-state init-state}} #{init-state})))

(defn init [c]
  (def capacity c)
  (def init-state (vec (repeat (count c) 0))))

(defn solve [capacity target]
  (init capacity)
  (first (for [path (extend)
               :when (some #(= % target) (:end-state path))]
           path)))

The part I don't like is init function. Most clojurians say that using def inside a function is bad. If I don't use init function, perhaps I have to add parameter capacity to almost every function in the code, which doesn't look pretty.

I was considered using nested function.

(defn solve [capacity target]
  (defn empty ...)
  (defn fill ...)
  (defn pour ...)
  (defn extend ...)
  ...)

However, using defn inside function is also bad, and the functions defined inside are actually not local functions, which are accessible outside the outer function.

Yes, there's letfn in clojure. I can put every function except solve into letfn. But in this case, the code is not very readable. I think letfn is only for short (which can be expressed in 1 or 2 lines) functions.

Perhaps there are better ways to do this. Any suggestions?

\$\endgroup\$
  • \$\begingroup\$ Do you have a link to the scala code? \$\endgroup\$ – abuzittin gillifirca Feb 13 '15 at 7:47
  • \$\begingroup\$ The link to the Scala code is mentioned in the @ben_rudgers' answer. Anyway, it's gist.github.com/yankov/5538283 \$\endgroup\$ – ntalbs Feb 13 '15 at 8:17
3
\$\begingroup\$

I won't try to be comprehensive:

The part I don't like is init function.

Your instincts are right.

If I don't use init function, perhaps I have to add parameter capacity to almost every function in the code, which looks not pretty.

Clojure supports dynamic binding, which you can use instead of misusing def; although I'm not sure it's warranted here.

Another problem I see is even though what you should do for each move (say [:pour 1 2]) is a constant, first it needs to be computed each time extend function is called, second look it up in a cond again in change. A move is a function from a state to a new state. Why not just use that function? Because we need the description for generating the history. So a move has a state transition function and a description.

(defrecord Move [description change])

And we can generate moves like this:

(defn moves [capacity]
  (let [glasses (range (count capacity))]
    (concat
     (for [g glasses] (Move. [:empty g] #(empty capacity % g)))
     (for [g glasses] (Move. [:fill g] #(fill capacity % g)))
     (for [from glasses, to glasses :when (not= from to)]
       (Move. [:pour from to] #(pour capacity % [from to]) )))))

We don't need change function anymore:

(defn extend-path [path move]
  (-> path
    (update-in [:history] #(conj % (:description move)))
    (update-in [:end-state] (:change move))))

If you pay attention, change function was dependent on what the specific moves were. Previous version of extend-path was dependent on them also, transitive as it was dependent on change. We will return to this, later.

We don't need to pass capacity to extend anymore; instead of generating moves, we can just pass them in:

(defn extend
  ([moves paths explored]
    (if-let [more (for [path paths
                        next-path (map #(extend-path path %) moves)
                        :when (not (contains? explored (:end-state next-path)))]
                    next-path)]
      (lazy-cat paths (extend moves more (conj explored (map #(:end-state %) more)))))))

Thus extend is not dependent on the specifics of this problem.

If we inline init we get something like this:

(defn solve [capacity target]
  (let [init-state (vec (repeat (count capacity) 0))
        moves (moves capacity)
        init-path #{{:history [], :end-state init-state}}]
    (first (for [path (extend moves init-path #{})
                 :when (some #(= % target) (:end-state path))]
             path))))

I initialize the explored states as empty set, as it made more sense to me.

I notice that the body of solve has only the test in the :when clause left specific to this problem. The rest of the body is actually some search algorithm. (I assume it is breadth-first)

we can extract it, too:

(defn breadth-first [moves init-path final?]
  (let [init-path #{{:history [], :end-state init-state}}]
    (first (for [path (extend moves init-path #{})
                 :when (final? (:end-state path))]
             path))))

(defn solve [capacity target]
  (let [init-state (vec (repeat (count capacity) 0))
        moves (moves capacity)
        final? #((set %) target)]
    (breadth-first moves init-state final?))

This enhanced separation of concerns, as breadth-first, extend, extend-path, Move are no longer dependent on the specifics of this problem. You can move them to another source file, which would not change much as the problem requirements evolve. This also makes it easier to change the search algorithm being used.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Warning: The following is opinionated at times. At other times it is more opinionated.

Channeling PG

I've heard on the internet so it must be true, that Paul Graham will get right to the point when interviewing applicants to Y-Combinator with "What problem does this solve?" It's hard to understand code without understanding what it is supposed to do. And only Google and watching a video twice make me think I might. Since I still don't understand the code though, I can't tell whether it solves the problem or not.

The "water pouring problem" is a canonical toy problem in programming curricula. Wolfram Mathworld describes it as a special case of the three jugs problem. The special case is where the third jug:

   capacity = +infinity
   contents = +infinity

The infinite capacity of the third jug allows it to represent a sink into which the contents of the other jugs may be emptied. The infinite contents allows the third jug to represent a faucet for filling other jugs.

The problem Ordersky presents is none of these. It is a generalized case based on a Python example from Peter Norvig's Design of Computer Programs course at Udacity. The problem Odersky is solving has an arbitrary number of jugs with finite capacity plus one jug with infinite capacity and contents. I would like to dub this the "n+1 Jugs Problem" because 1 captures the sink/faucet and n+1 hints at the notion of +infinity [at least in my little world].

Readability

A joke: I married my wife despite her adamant unwillingness to change her name. What's the big deal about being called "Donna" to match my tattoo?

Rich Hickey invented Clojure to help working programmers write good programs, not to give the world another excuse for tribal tattoos. I don't think init or def inside a function are big deals. They're very Pythonic and they couldn't make the code less readable for idiots like me.

Chiapas

I found the code opaque. "What is state?" I asked myself. I could look at the code for hours and never really figure it out. It took a half hour of concerted effort involving Google and watching a video of Martin Odersky...twice before I came up with a good answer: state is a vector of integers. In Ordersky's code this is explicit at line 6:

 type State = Vector[Int]

That's just standard Scala. It's fast in the sense that many people will understand it as soon as they read it. The Clojure implementation, on the other hand, is really slow because the source code doesn't make the nature of state clear. A [more opinionated][more opinionated] approach might be:

 ;;;; The state is a vector of integers.
 ;;;; Each element represents a glass.
 ;;;; The value of each element represents the contents of the glass.

A more direct implementation of the Scala code might use int-array for both state and glasses. There's nothing wrong with using types to make writing correct clear performant code easier.

Recommendations

Think about how much effort Odersky invests in making his code understandable. There's thirty minutes of video. There's the hours of video that come before it in the course sequence. The coding session starts with diagrams explaining the problem. Those are habits that are worth emulating. Following what Clojurists on the internet espouse doesn't make one an expert [I am aware of the irony]. Clojure is the product of Hammock Driven Development.

Extension

I'm a big fan of Lamport's idea specification as the starting point. One of the issues with Odersky's generalized approach is that it doesn't quickly trim the search space. Consider the case with two glasses:

 (def capacity  { :a 1
                  :b 100})
 (def target  50)           ; edit: early version used 99

The solution exists in the 99th layer of Odersky's onion because it requires 99 moves. With two glasses There are only six transition operations at each level of the onion:

 ; empty a
 ; empty b
 ; pour from a to b
 ; pour from b to a
 ; fill a
 ; fil  b

Yet the brute force search would cover:

 level | paths
 ------|-------
 1     |  2
 2     |  12
 3     |  72
 4     |  432
 ...   |  ...
 99    |  3.6295479083337274E76 = (6^99)/3

At an arbitrary iteration some may lead to states already visited and Odersky's approach trims those. What it doesn't do is capture the semantics of bags to trim the search space. Consider:

 (def capacity  { :a 1
                  :b 100
                  :c 1
                  :d 1
                  :e 1
                  :f 1})
 (def target  50)           ; edit: early version used 99

Many of the (Math/pow 42 99) states turn out to be equivalent and finding these equivalences would greatly reduce the search space and make for a more performant algorithm. For the purposes of Odersky's course [promoting Scala and functional programming] looking at algorithmic improvements is outside the mandate. For general code such as that under open review, it really isn't.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.