Sunday, July 16, 2017

Log 071617

Right. I managed to implement the N-Queens problem which the interpreter solves in around 13 seconds, GHC just promptly delivers the solutions.

That either implies I have a very slow runtime -which I know- or GHC sneakily also enjoys the benefit of lazy evaluation on this problem. I.e., I don't understand the solution I translated but the standard functional approach is to generate all board positions and filter out all admissible ones. GHC might benefit from lazy evaluation in that it doesn't need to produce all board positions but just needs to inspect whether a partly constructed solution is admissible according to the constraints, that would give almost back-tracking behavior on the solution space. (If I got it correct, the solution space is over-constrained, you only need 92 out of roughly forty thousand solutions. It helps a lot if you can swiftly dispose of most of them.)

Anyway, this task is far too complex for where the Egel interpreter is now in its development. I decided to implement the solution to a far more trivial problem, Euler project's task one. Sum all the integers from one to a thousand which are dividable by either three or five. Below the code, without the prelude primitives.

namespace ThreeOrFive (

    using System
    using List

    def sum = foldr (+) 0

    def three_or_five = [X -> or ((X%3) == 0) ((X%5) == 0) ]

    def euler1 =
        [ N -> (sum @ (filter three_or_five)) (fromto 1 N) ]

)

using ThreeOrFive

def main = euler1 1000

No comments:

Post a Comment