aspose file tools*
The moose likes Clojure and the fly likes Creating a cartesian product with to lists Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Languages » Clojure
Bookmark "Creating a cartesian product with to lists" Watch "Creating a cartesian product with to lists" New topic
Author

Creating a cartesian product with to lists

M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Hi,

i have two list with values like [a b c d] and [1 2 3 4] and i want to call a function with all possible combinations. i tried this:

But this gives me only one object: {:number 1 :letter a}.
How can i solve this problem?
Thank you
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

Try:

BTW, pmap is only worthwhile for very compute-intensive operations otherwise the coordination overhead of the parallelization will overwhelm the time spent actually doing something...
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Thank you, that did it. I believe you if you say, that in this case pmap is slower, but it still would be interesting to know how i have to write it with (p)map.

But i have another question:
I want to use a filter with a list and the list has structs with :names. In theory, the filter works, but when i use a variable with a list that is created in a function, it doesn't work:
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

Well, map and pmap are interchangeable in terms of functionality - the only difference is pmap will break the seq into chunks and map the function across them in parallel and then reassemble the mapped chunks into a single seq.

I have code that processes large log files and the process is fairly compute-intensive. With map, each file takes about two minutes to process, with pmap it takes just over half that. But the sequence is 400k to 500k elements long and the function being mapped is very heavy on the database. In general, I'd recommend using map and if you have long sequences and complex functions, try pmap - but time both implementations.

Back to your code: you're defining listtest2 as createList which is just another name for the function. In your filter form, you'd need (listtest2) instead of just listtest2 - you need to invoke the function to get the list.
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Okay, i have another thing that doesn't work:

I have a list and want to add structs to the list, but it doesn't work like i thing it would work.
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

First off, I think you want:

Then for binds variables n1 and n2 to successive elements of names and numbers respectively.

Second, you have:

But list is a built-in function - unless you've already redefined it to be some value?

Third, the result of your for expression will be a series of lst + pair values. I suspect you are trying to create a sequence of the pairs instead?

Perhaps what you want is:

That will give you a sequence of whatever the result of createPersons is (although I'd expect a singular function name there?).

Also, in Clojure, camelCase is not considered idiomatic so create-person would be more natural.
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
You are right, that's what i wanted, but i still have a problem
This works:
This doesn't:
In the first block of code, lst contains a sequence with all persons and numbers, in the second one it just contains the name of the list.
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

Did you mean this?

You need to call create-persons to get the list, otherwise you're just def'ing lst to be an alias for the create-persons function.
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Yes, that's exactly what i meant.

Next question, concerning this line:

Why doesn't this work:
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

That checks whether :name (a keyword) is equal to "Paul" (a string).

#(= :name "Paul") also does not use its argument (no use of % in that form).

(:name %) extracts the value whose key is :name from the map passed as the argument (%).

#(...) is an anonymous function whose arguments are named % (or %1), %2, %3 etc.

(filter ...) takes a function and a sequence and returns a sequence for which applying the function yields truthy.

Hope that clarifies / makes sense?
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Yes, now i understand the difference.

The next question i have is more in the direction of concepts of functional programming, where i don't know how to proceed since i have a Java background:
I have struct-map like person which has names and ages. I would like to do something like this:

I know it is not normal to change a name of a person, but thats not important here. In Java i would write person1 = person1.changeName(...); to change the object. In Clojure, i could write something like this:

But is this a good style?
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
I have another problem: I have a struct called house which contains a list with persons and a person is also a struct. I want to access it like this:

In the second case it is not okay that i get an array map, because now i need to work with the specified structure
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

I'll tackle this in several pieces. Let's start with the philosophy:
M Bryan wrote:The next question i have is more in the direction of concepts of functional programming, where i don't know how to proceed since i have a Java background...

One of the biggest conceptual challenges for folks coming to function programming is the tension between the focus on immutable data structures and our desire to "get things done". In particular, if we have a strong OO background, our way of thinking is completely focused on get an object, do a bunch of stuff to it (to change its state), put the object somewhere. It's a very imperative approach and we're so used to "modifying stuff" that we tend to forget about time and how history works in the real world...

In an OO world, when we change an object, we no longer have the old object - we have a single object and only one view of it: the "now" view. In a functional world, we have the history of each entity because we don't destroy things by changing them - we create new versions of each entity thru the application of transformations. Where we touch mutable state (such as a database), we have the option to retain that history or to destroy it, depending on our needs.

If you have a person, me, represented as a map {:name "Sean" :age 49} you would create a new map from that with new values as needed, e.g., (assoc me :name "Peter") and operate on that instead of the original. Your program then builds up as a series of transformations applied to data. You focus on "What am I going to do with this data?" instead of "What am I going to do to this data?".

It's more typical in a functional world to have change-name simply return a new "person" with the new :name value and just operate on that result (instead of trying to operate repeatedly on the original named entity). Again, with a focus what you're ultimately going to do with this new person, rather than what you're trying to do to the old person.

It might also help to think of def as binding a label to a value rather than declaring a "variable" and initializing it?

Does that help?
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

Now let's look at your house / person example. You're not providing us with all the pieces so let me make some assumptions and offer a possible model for the data...

A house is represented as a map with a number of different attributes. We're interested in occupants and that's a sequence of person entities. A person is represented as a map with a number of different attributes, including name.

We'll define some convenience accessors:

Now we can get the names of people in a house:

Arbitrary single occupant:

Name of arbitrary single occupant:

Looking at your compiler error, I suspect you're focusing on types rather than using generic maps and vectors, so you're restricting how you can operate on the data. It's more idiomatic (and a lot easier) to work with generic data structures first and then move to deftype / defrecord only if you need Java interop or extra performance (BTW, struct, struct-map and create-struct are deprecated in Clojure 1.3 in favor of records).

I'm puzzled by your def of get-person and get-name. What is accessor? You call get-person and get-name as if they are functions that take a map (and return a value) but that would mean the accessor function would have to return a function... yet it also seems to take a map and a key as arguments?

You're also calling first on the result of get-name - I'd expect get-name to return a string so first would return a character. So I wonder if you're storing :name as ["Sean" "Corfield"] so here's my example revised with that data format instead:

Hopefully that helps you?
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

BTW, suppose we have a friend:

and he moves in with us:

Note that this returns a new house with three occupants:

our-house still exists, unchanged, as it was before Sam moved in. This new household setup is available for us to work with (perhaps we'll store the new setup in MySQL and "destroy" the historical version (by overwriting it), perhaps we'll store the new setup in CouchDB and retain the prior version?).
M Bryan
Ranch Hand

Joined: Jun 15, 2011
Posts: 64
Yes, your answer helped me, you have been a great help! I have rewritten my code using records, it really is easier now. But do people with an imperative background get used to functional programming? ;)

I'm trying to learn functional programming by trying to write the game of Four wins (or is connect four the correct name?). I want to have an artificial intelligence, which, after a player's turn, calculates all possible outcomings and then decides the best decision.

I have a function which is called after a player's turn, where the computer should start six new games and do every possible action:



This is how i planned doing this, but it seems kind of ugly to me, it doesn't feel right.

1) Is there a nicer way of saving the seven calculations? Saving them in seven variables seems very imperative ;)
2) This could be done parallel by using pmap i suppose:



The syntax may not be correct, but i want to stress another thing: With pmap i can call a function several times at the same time, but what if i want to call several functions the same time, like this (in an imaginary syntax):



3) I tried to write a function using & more but it doesnt work:

Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

I'll answer Q3 now and come back to the others later when I have a bit more time. When you have & more in an argument list, Clojure binds that argument name to a sequence of any additional argument values supplied in the call. That means that your recursive call to moretest gets exactly one argument which is a sequence. What you need is (apply moretest more) in order to call it with "n-1" arguments.

When calling (moretest 1 1 1), i is bound to 1 and more is bound to [1 1] so in your code you'd have (+ 1 (moretest [1 1])) but with (+ 1 (apply moretest [1 1])) you get this instead (+ 1 (moretest 1 1)).
Sean Corfield
Ranch Hand

Joined: Feb 09, 2011
Posts: 267
    
    5

Now we'll do Q1... You normally do not do def inside defn. def (and defn) create top-level bindings of names. And you're right that even saving them as seven (local) variables is kinda ugly and not a very functional way to do it. Probably the hardest initial step in solving a problem like this is figuring out a coherent data model for the problem. You have an ordered collection of slots (seven in your example but there's no reason you couldn't easily make the game work for more or fewer slots). Each slot contains an ordered collection of zero or more tokens. A token is just a "yours" or "mine" thing so let's call those :red and :blue (which I believe are the two token colors in the original).

Since we want ordered collections, vectors are probably our best bet. We can access any item in constant time and easily append to the "back" of a vector using conj.

To play a token onto the board, we can use this function:

We need a method to figure out if the game is over. Let's assume we've written that and given a board, it returns :red, :blue, :none or nil for a red win, a blue win, a full board or a game in progress. That choice allows us to check (game-over? board) and if it's truthy, we have a result (:red, :blue, :none), else - it's falsey - we continue playing.

The computer's logic can be pretty complex since there are several scenarios:
  • pick a column that is a win for the computer
  • pick a column that does not create a possible win for the player
  • pick a column that lets the game continue

  • and you can get the computer to simulate up to any number of rounds of lookahead.

    What does one turn of analysis look like? Perhaps like this:

    This attempts all possible plays to get all new board setups, then checks whether any of those are a result. I'd probably actually use map-indexed to get a sequence of column numbers and results since that makes it easier to figure out the best column:

    Now we have a sequence of vectors, each vector has the column number and the result so we can filter on this or we could sort it using a comparator that works on game results.

    We could generalize this to repeatedly play alternate tokens up to a certain depth and return a sequence of column number followed by the sequence of results from each depth of play. That would allow quite a bit of intelligence in our computerized player. In fact, if you let it play until no more moves are possible (each column is full), you probably have an unstoppable opponent

    I'm going to leave it at that point for now. You'll note that the key things are: treating the game representation holistically instead of as individual columns; not worrying about parallelization (yet).

    So that's sort of the answer to Q2 as well: don't worry about parallel execution. When you have a complete solution using map, run some timing tests comparing map to pmap for any computationally intensive applications. Parallelization has quite an overhead (chunking the input, marshaling it across threads, reassembling the results) so unless your function is quite expensive and/or your collection very large, it probably won't be worth it.
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    M Bryan wrote:But do people with an imperative background get used to functional programming?

    Yes, don't worry, you'll get there. The hardest part to "un-learn" is the OO thinking, more so than the imperative nature of OO. In OO, the focus is on mutating encapsulated state so everything revolves around poking objects to make changes. In the functional world, you have to focus on coherent data models (just as you do in OO), but with holistic transforms from state to state instead of a narrow focus on mutating "just one thing at a time".

    Luckily Clojure has only a few core data types (vector, map, set) and they have a very consistent API so it's fairly easy to learn the vocabulary and start thinking about how to transform collections into new collections. The rest flows from there.

    In the "Connect Four" example, I initially wanted to (map (comp game-over? (partial play board my-token)) (range (count board))) but then thought I might want the new boards separately so that I might play additional turns on each board (creating a tree of results). Since playing a token is a simple operation and computing game-over? is more complex, it might be easier to generate all possible boards over the next N turns and then apply game-over? across those, breadth first, to find my wins and just return the first one. Since it's all lazily evaluated, we don't really need to worry about the cost of non-win situations if we go breadth first since we'll find our best move in the minimum number of turns and then won't actually realize the rest of the game's possibilities. That's an example of holistic transforms from state to state - since it is feasible to generate all possible moves for an entire game.

    It occurred to me that having the computer explore both sides means that you'd need a quick way to get the next player's token:

    Using this, (opposite-token cur-token) yields the next token in a simple map lookup (since maps can behave like functions).
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    Thinking on this a little more, I think I'd make play a bit smarter and introduce the concept of an invalid move/board. Attempting to play on an invalid board just returns invalid again. Attempting to place a token on a full column also returns invalid. A useful representation for invalid is nil.

    This has the nice property that once an invalid move is attempted, any future play attempts are the identity function (they also return nil). Using nil lets us write code that only needs to consider valid conditions - when evaluates to nil if its condition is falsey.

    Now at each stage of the analysis, we can shrink the possible set of moves down to just valid moves by doing (remove nil? new-boards).

    Given that we probably want to report the actual move we took, rather than just what the resulting board looks like, we might want to enhance our world representation to be something like this:

    That would only require minor adjustments in our functions, such as play:

    Our filter to remove invalid options is unchanged (we only return moves + board if it's valid, else we return nil).
    M Bryan
    Ranch Hand

    Joined: Jun 15, 2011
    Posts: 64
    I am overwhelmed by your answers! I think i need a few days till i understand every concept, because as you know i still have to get used to functional thinking ;)
    M Bryan
    Ranch Hand

    Joined: Jun 15, 2011
    Posts: 64
    After spending the whole day in the library learning for an exam, i found a little time working on our game



    I think the check-seq-for-winner function is quite good. It gets a sequence (row, column, diagonal row) and counts the consecutive colors.
    check-columns-for-winner get all the columns of the board an gives them to the function via map.
    get-nth-row is supposed to get every nth element of a column to get a row. The resulting rows shall be given to check-seq-for-winner.
    the map call in get-rows is returning a map. should i use another map call in the same line, calling check-seq-for-winner?
    And the bigger question: how do i get the vertical lines?

    Another thing:


    Where does item come from?
    To get the slot with the biggest propability for winning, we have to count how many games are won and lost with an specific decision, get the avarage (possibile-decision / games won) and return it. When having calculated all possibilities, we have the propabilities for every slot and the computer chooses the one with the highest and then it's the players turn again
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    M Bryan wrote: Where does item come from?

    Quick answer now, longer answer later...

    Sorry, mistake on my part - it should be map-indexed in that code, not map. map-indexed is like map except it calls the function with two arguments: an index into the sequence, and the current item in the sequence. I said map-indexed in the paragraph above but didn't fix the code I'd update it so it makes sense but that post is too old now...
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    I haven't tried your code but I'll show you my thinking on this...

    One thing I observed was that if you start at any position, you can figure out how to go in any direction using a for loop across multiple vectors and then filter results based on having tokens in enough positions. It's kinda brute force but I think it will work...

    Here's the for loop to generate the offsets:

    You can use these pairs to pull out the tokens - take the [x y] pair and keep going in that direction until you hit something other than the token you started on, then filter out sequences less than N long.

    That's a bit vague but it's the direction I'd probably go. I need to bash on it a bit in the REPL to figure out the details
    M Bryan
    Ranch Hand

    Joined: Jun 15, 2011
    Posts: 64
    IWhile learning for my exams the last day and spending one day at work writing Java code, i started to think about Closure:
    The key difference in my eyes is, that i don't use variables to save intermediate data. In fact, i use several functions in one line, which does not contribute to readable code. When i would save every step in a variable, i would go in the java direction and have more readable code. One thing missing would be objects with methods. In Clojure i write methods (called functions) which do work for objects (called records, structs, ...). But i am starting to think: where are the advantages? Is Clojure a lot faster than Java? Is it easier to develop when i'm used to Clojure?
    What about Scala: Scala is a functional language that uses objects. (It is described as a language, that is at the same time imperative and functional, but isn't this paradox?
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    It's easier to develop thread-safe, concurrent code in Clojure than in Java but many people find it easier to write procedural / imperative code than functional code because, well, mostly because that's what they're used to and it's always easier to do what you know.

    Most programmers today are used to OO as the de facto standard way to write code and there's so much literature out there for that - and it's usually what folks get taught in college too - so writing imperative OO code seems "natural": mutating objects to change the state of the world.

    But it wasn't always that way. When I started, I initially learned assembler and BASIC and C. Then Pascal (long before OO Pascal). Then some FORTRAN and COBOL, and a bit of PL/1 (and pl/p - Prime's system programming language). I did quite a bit of Algol 68 at college too. Then for my final year project I wrote an APL interpreter and a friend of mine wrote a Lisp interpreter. I stayed on to do research and focused on functional programming, creating a language called SURE (Surrey University Recursive Evaluator). SASL was around at the time, later Miranda. ML was around too.

    I left to do commercial C programming (all of the above was at University, except for the COBOL), then more assembler and COBOL. Cfront E (Education Edition) appeared in 1984 and gradually C++ became popular. I switched from C to C++ in 1992 and struggled with the switch from a mix of procedural and functional programming to OO. In 1997 I picked up and then switched to Java. I experimented with Haskell on the side, to keep my functional skills alive, and Prolog too. In 2008, I picked up Groovy and got a little functional programming in around the edges, then Scala in 2009 and Clojure in 2010.

    It's taken me a while to redevelop my functional thinking and I'm just beginning to get comfortable with it again, working with Clojure every day.

    So, for me, it's gradually becoming easier in general to write in Clojure.

    Clojure has polymorphism and type extension, but also has higher order functions and that's the abstraction that brings the power and conciseness. You can actually construct a full OO abstraction if you want (in about 40 lines of Clojure - we did it as a group exercise at one of the Clojure training days I attended, run by Amit Rathore, and it's featured in his book).

    I often use let in Clojure to save intermediate values to make expressions simpler - whatever makes code more readable. I haven't had much need for records yet, preferring to work with generic maps and vectors (structs are deprecated, BTW, superseded by records). I haven't used protocols either, but I have used multimethods - which greatly simplified what would have been a fairly complex finite state machine problem.

    As for Scala, it's a nicely constructed language, allowing you to write pure OO code, or basic procedural code, or fairly solid functional code. A true multi-paradigm language, much as C++ is multi-paradigm rather than pure OO. After working in Scala for a while, I got tired of the type system - I guess I'm just not a fan of static type systems and I find they slow me down when I'm prototyping code. It's why I found Groovy such a breath of fresh air after years of Java but Groovy's performance suffers as a result. With Clojure 1.3 having the same native primitive types as Java, calculation-intensive code can be as fast as Java, whilst bringing much more expressiveness (more than Groovy and, I believe, more than Scala too).

    My experience with introducing people to Clojure has been that the more OO experience they have, the harder it is to learn effective functional programming - but I definitely think it's worth the effort
    M Bryan
    Ranch Hand

    Joined: Jun 15, 2011
    Posts: 64
    Well, my programming background is not as impressiv as yours, but i'm a bit younger:
    When i was 14, i tought myself HTML and PHP and started to design small wegpages and made my own little browsergame. In school and university i learned Java. Additionally, i took a closer look at C/C++, but i never got the concept of pointers and havn't seen the necessity. A year ago i started working as a programmer (besides studying) in a small company where i'm currently working on GUI developement. Friends of mine had a subject called "functional programming", we talked a lot about it and the opinions where all the same: Since we all have an imperative background, because in school and university Java is tought first, they had problems getting used to the way of thinking. They think functional programming has nice concepts, like giving functions to another function. After this discussion, i got a book about Scala and Clojure from the library, read them and tried to work a little bit with Clojure (Scala has all the imperative things like Java and i wouldn't develop other code in Scala :wink. The thing i like most about Scala and Clojure (and probably all other functional languages) is, like my friends mentioned, the ability of giving functions to another function. I once missed that when developing at work
    I think in october i will also go to the functional programming subject to see advantages of functional programming. Now i'm still sceptical. When switching a programming language, i expect faster programs or faster development. I can't tell if Clojure programs are much faster than Java programs, but for now, it is very difficult for me to program in Clojure. But this doesn't count! I also had to learn to program with Java, so what i mean is: In what language do you think can one faster program, if he knows both, imperativ and functional programing? I am interested in the constructing a full OO abstraction in 40 lines. Do you know any articles with examples?
    Sean Corfield
    Ranch Hand

    Joined: Feb 09, 2011
    Posts: 267
        
        5

    Lots of questions there!
    M Bryan wrote:...because in school and university Java is tought first, they had problems getting used to the [functional] way of thinking

    Yes, I think the shift from teaching low-level programming and functional programming to only teaching Java / OO has been bad for the industry.
    M Bryan wrote:When switching a programming language, i expect faster programs or faster development.

    The fastest code is likely to be assembler but almost no one programs in that these days. We trade off performance for other factors. When you first pick up a new language, you're nowhere near as productive as the language you already know and use every day. If you've been programming in Java for two years (say) and you had folks teaching you that to get you started, then for a different way of thinking that you're having to teach yourself, it's probably going to take you at least two, probably three years to become as fluent in something like Clojure - but because it's a much higher-level language than Java, once you get productive enough in Clojure, you'll be able to produce much simpler, much more concise and much more maintainable code and, ultimately, you'll be solving problems much faster because you have to create an order of magnitude less code. But it takes time.
    M Bryan wrote:I can't tell if Clojure programs are much faster than Java programs

    Raw performance really isn't very important these days - machines are very powerful and no one wants to program in assembler (see above).
    M Bryan wrote:it is very difficult for me to program in Clojure

    Yup, which also makes it hard to objectively compare Clojure and Java since you feel you are much less productive in Clojure at the moment and you don't yet know enough of the subtleties in Clojure to create high-performance programs.
    M Bryan wrote:In what language do you think can one faster program, if he knows both, imperativ and functional programing?

    As an example, I paired with a colleague the other day to look at a data analysis problem he was working on. It involved taking two large data sets and merging them in a very particular way in order to produce date-ordered graphs. He knew the imperative way to do it and he could have bashed out the code in an hour or so - and he knew it would be dozens of lines of loops and conditionals and probably not very efficient. In about 10-20 minutes of pairing, we'd developed three "one-line" functions in Clojure that did exactly what he wanted, and it was pretty efficient.

    So, yes, I think if you know functional programming well enough, you can be much more productive. It's also worth bearing in mind that sometimes an imperative solution is simpler / faster / easier to create and functional languages let you do that too (it's just not idiomatic).
    M Bryan wrote:I am interested in the constructing a full OO abstraction in 40 lines. Do you know any articles with examples?

    The full version is in Clojure in Action, Amit's book, chapter 14 (14.3.4 An object-system for Clojure) but you can see a rough cut of it here, from the "Day of Macros" training course I went to, run by Amit: https://github.com/seancorfield/macro-day/blob/master/src/day/clos.clj

    Feel free to clone that repo and play with the code. It's a mix of code I created myself during exercises and solutions I copied off the whiteboard.
     
    Don't get me started about those stupid light bulbs.
     
    subject: Creating a cartesian product with to lists