Fork me on GitHub
#clojure
<
2020-09-13
>
didibus07:09:52

@zackteo This what I got

(def data [1 2 6 3 17 82 23 234])

(defn recursive-comb
  [kset-index nset-index nset kset func]
  (if (neg? kset-index)
    (func kset)
    (doseq [i (range nset-index (- (dec (count nset)) kset-index))]
      (recursive-comb (dec kset-index) (inc i) nset (assoc kset kset-index (get nset i)) func))))

(defn combinations
  [n k]
  (let [nset (vec (range (inc n)))
        kset (vec (repeat k 0))
        res (atom [])
        func #(swap! res conj %)]
    (recursive-comb (dec k) 0 nset kset func)
    @res))

(defn all-combinations
  [n]
  (mapcat #(combinations n %)
          (range (inc n))))

(defn smallest-pair
  [ints sum]
  (let [indices (all-combinations (count ints))]
    (reduce
     (fn[acc e]
       (if (= sum (reduce + (map #(get ints %) e)))
         (reduced e)
         nil))
     0 indices)))

(smallest-pair data 26)
(smallest-pair data 40)
(smallest-pair data 23)
Credit mostly goes to this MATHLAB solution I adapted from: https://stackoverflow.com/a/35689122/172272

zackteo07:09:16

@didibus Thanks 🙂 Let me try to take a look at it!

wombawomba08:09:46

So I have a laziness-related issue. Basically, I have this recursive function that builds a lazy seq of all possible solutions to a problem, by recursively calling itself with a smaller problem (to get all solutions to the smaller problem) and then appending all solutions to the ‘bigger’ problem to each solution of the smaller problem mapcat (think dynamic programming). Because generating solutions is somewhat costly, I would like the generated seq to be completely lazy (as in, if I ask for one solution, it just computes one solution to each sub-problem). However, this doesn’t seem to be the case — something’s forcing at least a significant amount of solutions to be generated. Now, I think that mapcat is probably the problem here, because it seems to do some sort of chunking. I’d like to write an equivalent that never realizes more elements of the colls than what is needed. So: is there a way to write such a ‘completely’ lazy mapcat?

wombawomba08:09:33

Here’s an example of how mapcat seems to realize the first coll eagerly:

> (def a (mapcat #(for [x %] (do (println x) x)) (for [_ (range 10)] (range 10))))
#'my.repl/a
> (first a)
0
1
2
3
4
5
6
7
8
9
0
[cli.repl]> (second a)
1

didibus08:09:48

You can try this:

(defn unchunk
  [s]
  (lazy-seq
   (when (seq s)
     (cons (first s) (unchunk (rest s))))))

didibus08:09:41

(def a (mapcat #(for [x %] (do (println x) x))
               (for [_ (range 10)] (unchunk (range 10)))))

> (first a)
0

wombawomba08:09:41

Thanks @didibus! Alas, it seems the problem actually lies elsewhere
 I’ll keep looking 🙂

wombawomba09:09:19

I also have a loop on the following form, which seems to be causing some chunking:

(for [x xs
      y (f x)]
  y)
Is there a way to make this ‘strictly lazy’ (with regard to (f x))?

wombawomba09:09:05


I’m thinking (for [x xs y (unchunk (f x))] y) should do the trick, so maybe the problem is that f is being eager for whatever reason


wombawomba09:09:35

turns out the problem was that I was using schemas for the function outputs :face_palm:

Eugene Koontz14:09:05

had a similar problem (generating solutions by recursively generating and returning a lazy sequence of the solutions) - my implementation is here: https://github.com/ekoontz/menard/blob/master/src/menard/generate.cljc#L77

Eugene Koontz14:09:06

I guess I’m doing the unchunk in that function generate-all

dominicm12:09:16

I'm betting there's a nice trick to do {:a ["foo" "bar"] :b ["baz" "quux"] :c ["I'm" "out"]} => {"foo" :a "bar" :a "baz" :b "quux" :b "I'm" :c "out" :c}. My current solution involves a nested reduce. It's expected the the items in the vectors are distinct.

Jan K13:09:55

I would do (into {} (for [[k vs] input, v vs] [v k])))

dominicm13:09:01

I like that. I don't use that part of for nearly enough. Thanks!

Joe15:09:41

Hi all, I don't know whether this is the right place for this, but over the weekend I was watching some conference presentation that talked about the limitations of the 'text-editing/file' paradigm for source code. That got me thinking about about what a different approach could be, and I put down some thoughts about a product https://github.com/RedPenguin101/Formative. There is no code for this (and frankly I'm not capable of writing it), but I would be interested in peoples thoughts around this approach, which I think Clojure is uniquely suited for and plays to Clojure's strengths. Also interested if something like this already exists! Thanks much

Alex Miller (Clojure team)16:09:39

The old VisualAge editor for Java had a paradigm similar to this for single-method focused editing (I believe due to its roots as a Smalltalk environment). It was not a great fit for Java as you typically needed more context than a single method but would be better for Clojure. The graph stuff always seems like a great idea on small examples - in practice, there are practical limits to how much of a graph you can fit on a page and still have nodes be readable and edges understandable, particularly in cases of high fan-out/fan-in.

👍 9
chucklehead16:09:43

I shared this in #off-topic earlier this week, but somewhat relevant to your topic: here's a demo of the CEDAR environment from Xerox PARC showing off the state-of-the-art from ~1984 https://youtu.be/z_dt7NG38V4?t=2305 around here he starts demonstrating some of the general editor functionality and then gets into more of the developer functionality with navigating/editing/building code. The way he describes mouse navigation/selection granularity working may be of interest to you.

👍 3
seancorfield17:09:56

The original vision for LightTable was very much around functions but early trials indicated people found that hard to work with and it evolved into a more traditional editor. I remember back in the '90s, HP were working on a C++ development environment that was sort of along these lines, with editing focused on classes and drill down into methods. Very experimental stuff that ended up going nowhere I think, but it fed into HP's feedback about templates on the ANSI Standards Committee, and I got to see a prototype of it running at one of the committee meetings.

Joe17:09:44

Hmm, it does sound like it falls in the category of ‘if it worked, someone would’ve got it working by now’. Especially if lighttable already tried and abandoned it.

seancorfield18:09:23

Chris Granger talked about how LightTable had to pivot at one of the Conj's I think. Here's an indication of his original ideas about it https://www.chris-granger.com/2012/04/12/light-table-a-new-ide-concept/ and how much it drew on Smalltalk for that https://www.chris-granger.com/2012/10/05/all-ideas-are-old-ideas/ and this shows how it turned into a much more traditional editor https://www.chris-granger.com/2013/02/27/light-table-030-experience/

didibus00:09:23

What I think has more potential isn't a visual editor, but a more semantic aware editor where the editor guarantees that all edits always compiles and are valid syntax. I've thought about this before, but every-time you'd def, instead of using some text id which is the def name, the editor would provide an auto-generated GUID for it instead, and there's be meta similar to docstring that would be docname which is the name you'd normally be entering. That type of thing. I mean we get close-ish to this in Clojure already if you use strict strutural editing, but this goes beyond and assume your editor has lots of semantic knowledge, and the UI is not strictly letting you modify text free-form. Unison: https://www.unisonweb.org/ comes closest as I know to what I'm talking about.

didibus00:09:43

Recommend this talk about it if you're interested: https://www.youtube.com/watch?v=gCWtkvDQ2ZI

dominicm08:09:30

A little while ago I recall seeing a clojure editor like this

kennytilton02:09:13

“the limitations of the ‘text-editing/file’ paradigm”? Are we sure about that? As some famous language inventor once said, “Programming is not about typing.” Beware also the unreasoned embrace of decomposition; its prima facie appeal may ignore the way developers actually work with text. I can thrash out a hundred lines that would decompose into a fifteen node tree, and then decide, Naw, that won’t hunt. With a hundred lines of text I just slice and dice a refactoring in seconds, with a structural editor I am now fighting my IDE just to say what I mean. A good counterpoint here is that I have played with structural editors like Paredit and they are nifty, but I keep them turned off: fighting them at certain times is not justified by the keystrokes they generally save. Cue again the “not about typing” gem.

seancorfield03:09:20

Yeah, I think Aurora was more in the right direction than the early LightTable demos -- as intriguing as they were -- because Aurora operates at an entirely higher level of abstraction. But even then, I think the visual/symbolic development systems have a very long way to go before they're going to make any inroads into mainstream programming. Our "muscle memory" for traversing files and directories and viewing deliberately arranged groups of functions will take a huge amount of "better" before we shift...

Joe11:09:08

@U0PUGPSFR If I'm understanding the example you give about writing 100 lines of code (presumably in a function?) and then refactoring into several functions, it wouldn't be precluded by either structural editing or the 'form editor' approach. You could extract forms into new functions, or conversely, inline them. exactly as you would in a text editor. Both structural editing and form editors constrain the programmer_,_ but the goal would be to constrain in a way that encourages an opinionated view on the best way to do things - a very Clojure-ish thing I feel. Structural Editing, I think, is about moving 'up a level' in how we interact with forms, away from editing characters, which is a legacy of the how things are stored on the machine. What I would be interested in is trying to do the same thing with the file, another legacy of how things are stored on the machine. Obviously with both you introduce constraints. So I guess thinking about it more, 'limitation of the text-editing/file paradigm' is the opposite of what I meant - it's introducing limitations to those things in the name of creating a (subjectively) better experience.

Joe12:09:12

@U04V70XH6 interesting you mention the 'muscle memory'. The talk that prompted this was https://www.youtube.com/watch?v=8pTEmbeENF4, which is essentially about just that.

kennytilton18:09:33

No, @U0105JJK1L3. Not refactoring into functions. Just slicing/dicing text, during which process the text is not valid Clojure. The syntax highlighter is having a cow. Then I clean it up. Anything preventing me from mangling text is in my way. ie, You missed what I said about Paredit. Have you looked at visual programming tools from way back when? Definitely a tempting idea, but like I said, I keep Paredit turned off for a reason.

Joe19:09:39

Oh, I see what you mean - yeah I can see how that would stop structural editing being useful.

didibus22:09:11

@U0PUGPSFR You'd need to provide details, I feel all the slicing/dicing you're doing is probably covered by some structural edit which you don't know about. That said, I won't deny that we can figure our way to any edits more easily with only knowing a few text editing commands and that can be a friendlier experience. I recommend you watch the talk I linked to Unison. Because I don't think you're seeing exactly what I'm talking about. Text editing can be your interface of choice if you want, and it could be visual, or structural, or something else. When the program source is no longer textual, those things are just various UX you can build on top. What happens in unison is that your text files are not your source code. They are just an interface to them. And you cannot add a function which isn't valid to the source. Think a kind of per-function git commit, where you have a hook that asserts the function compiles to allow the commit

didibus22:09:44

In fact in Unison, you can delete the textual code, and then Unison can regenerate it for you, though it won't be exactly the text you typed, it will be the same function

kennytilton23:09:29

That video is a little rough. The win I saw was great, but fundamentally about being immune to bit rot, dependencies, versioning, and of course deployment. I will take a look at the doc and see if I can find anything about structural editing. But Unison looks like a nice solution for the bits I grokked. thx for the lead.

didibus01:09:06

Well, you're right, there's no structural editing per say, you can use the editor of your choice. But I'm not so much talking about the editing being structural as that the source code is edited in well behaving structures.

didibus01:09:25

Basically, until you add the function in the source, the function is not in the source. So I consider the add function command a structural edit of the source. And you cannot add a function that doesn't compile. And another example is renaming, you rename not by changing the name on text all over the place, renaming is also a structural command edit you run on the source, etc.

didibus01:09:33

Maybe I shouldn't say structural, maybe it's better to call it semantic editing?

Tom H.00:09:29

Folks interested in this stuff, come check out the https://futureofcoding.org/ community! There's lots of people in the slack working on similar projects

👍 3
kennytilton22:09:02

@didibus Natural language is tough. 🙂 I did realize we were talking about different things after a while. I was too hasty in thinking I knew to what you referred. Unison is intriguing!

💯 3
Joe13:09:32

@U06077728 Super interesting, thanks for the link!

Jeff Evans18:09:06

Cross posting this question since I think there is a decent chance any such library would be compatible with both
 https://clojurians.slack.com/archives/C03S1L9DN/p1599928442460000

phronmophobic18:09:37

have you tried instaparse? https://github.com/engelberg/instaparse . probably wouldn't be too hard to find/coerce a json grammar to work with it

Jeff Evans19:09:08

hadn’t heard of this. thanks, I will check into it

emccue18:09:33

question about the clojure implementation / java concurrency model

emccue18:09:10

since i am going through and trying to copy paste the core vector/map/set data structures in a more "java friendly" face

emccue18:09:44

persistent vector has a field for caching its hash code

emccue18:09:31

and on the first time through it will calculate it

emccue18:09:44

this._hash = hash

emccue18:09:56

is this assignment atomic?

emccue18:09:47

how can we know that two writes won't clobber each other in weird or undefined ways

andy.fingerhut23:09:39

If you put objects inside of a Clojure collection whose hash values can change after they are added to the collection, then there can be a data race there. Thus one should not do so.

andy.fingerhut23:09:10

Clojure's immutable values, including collections that contain only immutable values, never change their hash value once created, so they are all safe to put inside of such Clojure collections.

andy.fingerhut23:09:39

Putting mutable Java objects inside of such collections, and then mutating them later so their hash value changes, is a recipe for bugs.

phronmophobic18:09:20

if it's pure, does it matter? worst case is that some extra work is done.

emccue18:09:03

well, the extra work isn't an issue - that hash == 0 call can be false and it won't matter

emccue18:09:26

but lets say the hash code is 4 bytes (so we can reason about it)

emccue18:09:15

I don't know if that assignment could be read halfway through writing bytes

emccue18:09:35

so maybe it starts at 0000 and only 0100 has been written so far

phronmophobic18:09:10

assignments of ints are atomic

phronmophobic18:09:30

> another thread is guaranteed not to see a partially written int

Alex Miller (Clojure team)20:09:44

Assignments of all primitive types are atomic in Java (except the 64 bit longs and doubles - know commonly as “long tearing”)

Alex Miller (Clojure team)20:09:53

This pattern for setting the hash is racy, but safe as written - either you observe the computed hash or compute and store it, possibly writing over another threads value atomically

Alex Miller (Clojure team)20:09:25

Java Concurrency in Practice is a great book for stuff like this, well worth reading even if you’re not using Java

👀 3
chepprey22:09:28

Are pointers (object references) in a 64bit jvm also susceptible to tearing? Maybe I have it backwards, as in a long on a 32 bit jvm needs 2 separate machine ops to be assigned. So maybe a better question is: is tearing possible at all on a 64bit jvm, since the machine should be able to copy 64bits in one shot

andy.fingerhut23:09:06

Whether or not it is possible on a 64-bit JVM, I doubt anyone would recommend writing code that works on a 64-bit JVM but fails on a 32-bit JVM, since there are so few extra things needing care on a 32-bit JVM.

andy.fingerhut23:09:55

I will second the recommendation for the Java Concurrency in Practice book. Lots of info about what is safe in the JVM with multiple threads, and what is not.

andy.fingerhut23:09:59

This Stack Overflow question quotes a portion of the JLS (Java Language specification) that says that however a JVM implements object references, reads and writes of them must be implemented atomically.

Alex Miller (Clojure team)00:09:21

Object reference writes are always atomic

chepprey00:09:43

I'm certainly not writing (nor seeking to recommend writing) such code! I was just curious, I hadn't before considered the possible differences of tearing between 32/64bit jvms. On my specific question about long tearing on a 64bit jvm, the JLS appears to say tearing is technically still possible, as the copying of longs is JVM implementation dependent, so you may not officially depend on atomic longs.

emccue21:09:15

Hmm, a big chunk of what is in APersistentVector I can get for free with AbstractList

emccue21:09:04

a bit of hoopla for mutable lists that is wasteful, so clojure not using it makes perfect sense