combinatorsfactor-lang

How can I extract the redundancy in this Factor word definition with dataflow combinators?


I'm using the early ProjectEuler problems as a way to get to know Factor. Already in the very first problem I don't find a satisfactory solution.

I can solve the division test with this

: 3or5divisible ( n -- ? ) [ 3 mod ] [ 5 mod ] bi * 0 = ;

But what I don't like is the repetition of the mod. Of course it's only two times, but another problem might need to check 200.

I tried with map, curry, bi, 2bi, bi@, arrays and plain stack values etc. I always get a stack underflow or an effect mismatch (when using map). I have have not yet found a way to see the results of my trials in the inspector.

How can I factor that mod out and have it applied to { 3 5 } or an equivalent stack?
Cool would be two variants e.g. of a mod3and5 (including effect specification); one that leaves 2 1 on the stack for input 11 and one that returns { 2 1 }.


Solution

  • A general comment, sometimes duplicative code is more readable and sometimes higher level fancy code is better. The places where combinators can shine is when it eliminates stack shuffling that is harder to understand.

    So, perhaps if you start from simple stack shuffling:

    : 3or5divisible ( n -- ? )
        [ 3 mod zero? ] keep 5 mod zero? or ;
    

    Then see how it might look with simple combinators:

    : 3or5divisible ( n -- ? )
        [ 3 mod zero? ] [ 5 mod zero? ] bi or ;
    

    And see how it looks using named local variables, not bad:

    :: 3or5divisible ( n -- ? )
        n 3 mod zero? n 5 mod zero? or ;
    

    And then see how it looks using fancier combinators, maybe harder to read:

    : 3or5divisible ( n -- ? )
        3 5 [ mod zero? ] bi-curry@ bi or ;
    

    And then see how it works if you passed it a sequence of numbers to check, pretty easy to read (but perhaps slightly worse runtime performance due to iterating the sequence to find the numbers to be checked):

    : 3or5divisible ( n -- ? )
        { 3 5 } [ mod zero? ] with any? ;
    

    Or maybe using a macro to do code generation for arbitrary inputs:

    MACRO: divisible ( ns -- quot )
        [ [ '[ _ mod zero? ] ] map '[ _ cleave ] ]
        [ length 1 - [ or ] <repetition> concat ] bi
        append ;
    

    And then see that it makes the code you expect:

    IN: scratchpad [ { 3 5 } divisible ] expand-macros .
    [ [ 3 mod zero? ] keep [ 5 mod zero? ] keep drop or ]
    

    Lots of possibilities...