問題タブ [semigroup]

これは、基数ソートの擬似コードです。

これは、基数ソートの Scala コードです。

これは、基数ソートの Haskell コードです。

私の質問は次のとおりです。基数ソートのモノイドまたはセミグループを定式化できますか?

2 つの要素のセットに対する 2 項演算の回数は です2^(2*2)=16。
その集合に対する連想バイナリ演算の

数は 8 だけです。3 つの要素の集合に対するバイナリ演算の数は 3^(3*3)=19683 です。
そのセットに対する連想二項演算の数はわずか 113 です。n 個の要素のセットにいくつの連想二項演算があるかを知る方法は?

また、この 113 の操作をすべて取得してファイルに書き込むためには、プログラムを作成する必要があります。
19683 操作すべてを取得してから、19683 操作すべての連想プロパティ "a*(b c)==(a b)*c" をチェックすると、うまくいきますが、n には時間がかかります。 =4つの要素！
このタスクを解決するための効率的なアルゴリズムを作成する方法は?
私を助けてください！

Scalaz SemiGroup が共変でない単純な理由は次のとおりです。

https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Semigroup.scala

https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/syntax/SemigroupSyntax.scala

ありがとう。

これは私の前の質問のフォローアップです

Kleisli<=<(compose) と>=>(andThen)の 2 つの演算子を定義します。私にとっては非常に自然に見えますが、どのように役立つ>=>かわかりません。<=<

>=>また、半群がないように見えますA => M[A]が、<=<半群は存在します。

その背後にある理論的根拠は何ですか?

次のデータ型とセミグループ インスタンスがあります。

上記の型のモノイド インスタンスを作成したいのですが、その方法がわかりません。次の定義を使用する場合

への入力のすべてのペアで機能しますが<>、私がいるものを除きます。mappend

に評価されmemptyます。

memptyが有効になるようにこれを修正するにはどうすればよいですか? memptyが左か右かによって決まるため、新しい構文や概念がないとできないようです...

はじめに: グループのインフィックス製品

グループがあるとします

および要素のリスト

私たちの目標が機能を実装することである場合

そのような

i(そして>の場合に何が起こるかは気にしませんj)

次に、プレフィックスのテーブルを事前に計算することでそれを行うことができます

（1右側は の単位を示しますG）、次に次のように実装fします

これは次の理由で機能します。

など

十分な再結合の後。

私の質問

G が群ではなくモノイドにすぎない場合、この考えを救うことができるでしょうか。

私の特定の問題について、ifG = ([0, 1] ⊂ ℝ, *)、つまり、単位線からの実数があり、0で割ることができない場合に同様のことを行うことはできますか?

... または、Scala をコーディングしなければならない Haskell プログラマーの事故、パート 5.

私はScalaで次の構造を持っています:

Semigroupそして、Cats を使用して、そのインスタンスを定義したいと思います。

これにより、次のエラーが発生します。

したがって、私の推測では、Scala コンパイラーのインスタンスを定義しているため、 ofSemigroupのインスタンスを派生させることはできません。次のインスタンスがコンパイルされているため、これは確認されているようです。SemigroupMap[String, ResourceTree]

これが Scala でセミグループのインスタンスを定義する正しい方法である場合、この言語での FP の実行をあきらめるという考えを検討し始めるので、私が間違っていることを本当に望んでいます。

より良い方法はありますか？