5 ms·
This starts off well, but the Haskell makes it hard for me to understand. Perhaps I should learn Haskell?
by mehulashah 3y ago
This starts off well, but the Haskell makes it hard for me to understand. Perhaps I should learn Haskell?
- LukeShu 3y agoIndependently 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/inspect/rebuildmappings/kmp.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).
- nine_k 3y agoLearning 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.
- foobarian 3y agoIf 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.
- deleted 3y ago[deleted]
- lispm 3y agoLooks 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.
- pitkali 3y agoYes, 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.
- lispm 3y agoWhich makes it very different in Racket. STRING-REST creates a new string with the contents copied from the original string, minus one character.
- nine_k 3y agoMuch 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.
- ks2048 3y agoI recently began learning Haskell via Graham Hutton’s YouTube series. Recommended!
- epgui 3y agoI mean this is the Journal of Functional Programming... That being said, I wish more people had your response. Curiosity and openness are beautiful things.
- teo_zero 3y agoI 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.
- necovek 3y agoIt 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 :).
- mrkeen 3y agoI 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.
- mrkeen 3y agoProbably! -- 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); }
- mbwgh 3y agoThanks. I believe with the additional null checks, this version is safer to use, too!
- poorlyknit 3y agoThere's no null in Haskell to check for. Go check it out!
- poorlyknit 3y agoThis would be even more palatable if it involved some more design patterns.