view release on metacpan or  search on metacpan

docs/blog/perl-weekly-challenges-113.md  view on Meta::CPAN

    we're introducing. This doesn't just sound like a cycle, but it
    is: it creates the list that ends with its own beginning, looping
    `1`s infinitely. But in simpler terms: `let` in Haskell is always
    recursive, like the `my rec` that I kind-of suggested Perl could
    maybe benefit from. But because there is no non-recursive `let` in
    Haskell, if I really want to translate `my $l = cons 1, $l`, I
    have to introduce a new variable name, like `let l' = 1:l`. The
    apostroph can be part of variable names and is used to mean a new
    variable related to the old name (like derivatives in math).
    
  * Haskell doesn't have `undef`, instead I'm using the `Maybe`
    type—remember, I mentioned that <a href="#Maybe">above</a>, here
    you can see it in action. It means that e.g.

        Right $chosen

    becomes

        Just (Right chosen')
        
    because we have to explicitly wrap the value to become a Maybe
    type. `undef` becomes `Nothing`. The `catMaybes` function takes a
    list of `Maybe`s, and returns the elements that are `Just`s
    (i.e. dropping the `Nothing`s), but take the values out of the
    wrappings again.

  * pattern matching:
  
        unless ($solutions->is_null) {
            my $solution = $solutions->first;
            ...
        }
  
    becomes
    
          case solutions of
            (solution:_) -> ...

  * I'm using `Data.Set` instead of a hash table, `Set.fromList` is
    converting the list to a set, `Set.member` checks whether a value is
    in the set.
  
  * Haskell is using lazy evaluation by default, everywhere. That's why
  
        Left lazy {
            $check->($chosen)
        }
        
    becomes simply

        Left (check chosen')

It should now be straight-forward to see the equivalence of the
implementations.

Interestingly, the Haskell version, compiled with `-O2`, is only about
twice as fast as the Perl implementation. But to be fair, my Perl
version is using an array to hold `$ns`, wheras I use the linked list
in Haskell, and a hash table in Perl, whereas `Data.Set` is a tree in
Haskell. Also, since the algorithm finds most solutions with only very
few iterations, what we're mostly benchmarking is the setting up of
the initial data: the creation of `1..$N`, conversion to strings,
filtering according to `$D`, conversion to the hashmap/Set. This is
very optimized in the Perl core, and probably somewhat less so
(compared to other things) in Haskell. I'm also using `Integer` in the
Haskell version which is safe against wraparounds, but more costly;
replacing it with `Int` makes it about 1.5x faster, and is just about
as safe as Perl's ints are (propagation to floating point numbers
would break things, too, if it weren't academic on a 64-bit machine).

Like mentioned in the previous section, the code could probably be written
shorter by using the cartesian product or similar, I may look into
it. Also, someone on IRC posted me
[this](https://paste.tomsmeding.com/krsnrC8I) solution which is much
shorter, although it runs about half as fast as mine.

## Epilogue

Aside of the assignments to `($mydir, $myname)`, which are needed to
handle the compile time vs. run time phasing (which exactly does have
a bit of the evil-ish taste of spaghetti execution flow of imperative
programming), there is just one single variable mutation in either of
the two Perl scripts. Can you spot it?

Answer (rot13): Vg'f va `znlor_ercerfragnoyr` va gur ercerfrag_vagrtre
fpevcg: gur `znlor_pubbfr` inevnoyr vf orvat birejevggra.

There are zero data structure mutations, and the only I/O that the
Perl scripts are doing are via the `repl` and `run_tests` calls.

The advantage of that is that data consistently only ever travels in
one direction, from function arguments to function results. This means
that the movement of data is immediately evident from just the lexical
structure of the program—the dynamic behaviour of the program cannot
change that.

But note that I'm saying that *data flow direction* is
straight-forward; I don't say the same about *evaluation order*. Once
lazy evaluation is used, evaluation order depends on the dynamic
behaviour of the program.

But while we don't necessarily understand the evaluation order easily,
it doesn't matter for the correctness of the result. The correctness
of the result only depends on data flow, not on evaluation order. If
the program finishes, the result is more easily shown to be correct in
a functional program. A functional programming approach does *not*
help analyzing whether the program finishes or takes forever or runs
out of memory (except indirectly to some extent by more easily finding
data correctness issues, since bogus data can also be a source of
erratic evaluation order). It shouldn't hurt, either, but I'm not
going to make claims here. In any case, it's definitely different, and
the tooling to debug evaluation order in programs with lots of lazy
evaluation may be worse in Perl than in Haskell (although there is
some <a href="#fn4">[4]</a>), so I suggest to be careful and not go
over board with that. Use `lazy { }` and streams only where needed to
enable a purely functional programming style. Using `lazyT` instead of
`lazy` to make sure you're getting the right types of data can also
help.

## Footnotes