Hacker News Reader

Comment by mehulashah | Hacker News Reader

This starts off well, but the Haskell makes it hard for me to understand. Perhaps I should learn Haskell?

Independently of anything else: Yes, you should learn Haskell :)

If Go is more your speed, here's an implementation in Go: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/in... (though it is slightly complicated by the fact that it allows 'substr' to include fixed-length wildcards).

Learning some Haskell is very educational; it changes the way you think about programming, including daily code (much like a Lisp, Erlang, SQL, Smalltalk also do).

These examples use pretty minimal features of Haskell, mostly expressions, function definitions with argument pattern matching, and algebraic type definitions. These would take an hour or two to get acquainted with. Nothing fancy is used in the code, in particular, nothing outright monadic :)

For comparison, you can check out a Lisp version at the end. It's much longer, and Lisp (well, Racket here) is usually a very expressive language.

If Haskell seems too intimidating I think Standard ML is easier to wrap one's head around as it has fewer features. But it still delivers that FP way of thinking insight.

Looks problematic. Is a string in Haskell a list? I would think that in Racket a string is a vector. FIRST and REST operations then would have very different implementations.

Yes, the String is a list of characters. The Haskell code uses head and tail on it. In Racket, they provided string-first and string-rest (at the end) to replace those.

Which makes it very different in Racket. STRING-REST creates a new string with the contents copied from the original string, minus one character.

Much like in Rust or C++, there are several ways to represent sequences of characters in Haskell. The default way is a List, which is like a classic Lisp list,va chain of cons cells.

I had the same reaction! I was excited about this article before realizing that "only elementary functional programming techniques" promised in the abstract actually means a full programming language used by 1% of programmers.

Probably!

  -- The any function determines if some element of the input list satisfies the given predicate:
  any f     [] = False
  any f (x:xt) = f x || any f xt

In the meantime here's a more palatable version of 'any' for the 99% of programmers who are put off by the confusing Haskell:

    // Returns whether any elements of this stream match the provided predicate. May not evaluate the predicate on all elements if not necessary for determining the result. If the stream is empty then false is returned and the predicate is not evaluated.

    public final boolean anyMatch(Predicate<? super P_OUT> predicate) {
        return evaluate(MatchOps.makeRef(predicate, MatchOps.MatchKind.ANY));
    }

    final <R> R evaluate(TerminalOp<E_OUT, R> terminalOp) {
        assert getOutputShape() == terminalOp.inputShape();
        if (linkedOrConsumed)
            throw new IllegalStateException(MSG_STREAM_LINKED);
        linkedOrConsumed = true;

        return isParallel()
               ? terminalOp.evaluateParallel(this, sourceSpliterator(terminalOp.getOpFlags()))
               : terminalOp.evaluateSequential(this, sourceSpliterator(terminalOp.getOpFlags()));
    }

    public static <T> TerminalOp<T, Boolean> makeRef(Predicate<? super T> predicate,
            MatchKind matchKind) {
        Objects.requireNonNull(predicate);
        Objects.requireNonNull(matchKind);
        class MatchSink extends BooleanTerminalSink<T> {
            MatchSink() {
                super(matchKind);
            }

            @Override
            public void accept(T t) {
                if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
                    stop = true;
                    value = matchKind.shortCircuitResult;
                }
            }
        }

        return new MatchOp<>(StreamShape.REFERENCE, matchKind, MatchSink::new);
    }

Thanks. I believe with the additional null checks, this version is safer to use, too!

There's no null in Haskell to check for. Go check it out!

This would be even more palatable if it involved some more design patterns.

I recently began learning Haskell via Graham Hutton’s YouTube series. Recommended!

It would help if it was clear what tokens are part of the language or standard library, and what tokens are implementation of this algorithm (as in, some syntax highlighting would be nice :).

I think it this case everything is defined in the article, except for List, which is either an empty list [] or a non-empty list x:xs

Anything lowercase is a function/variable, and will appear somewhere on the left-hand-side of an equals.

Anything uppercase is a Type/constructor. In this case I think they've only used a Tree, which they defined themselves (either a Nil or a Node).

any and scanl would typically be imports, but they've defined these in full.

They also defined init themselves unrelated to the one in the stdlib.

I mean this is the Journal of Functional Programming... That being said, I wish more people had your response. Curiosity and openness are beautiful things.

Reply on news.ycombinator.com