Haskell (とElixir) でもMöbius関数を実装した

気に成ってHaskellでもMobius函數 (メビウス関数) を実装した。Elixir版も再掲する。
cf. Elixir (とJavaScriptとRuby) でMöbius関数を実装した http://c4se.hatenablog.com/entry/2013/07/12/210747 前回

Haskellをまともに書いたのは人生で初めてである。今まで書こうにも感覚的に、書けなかった。RubyのEnumerableを使いまわしてゐれば、あまり怖くはなかった。

HaskellでMöbius函數

compileが通った次の瞬間にtestも通って驚いた。好い事だ。ghciは便利だが、Elixirのiexも便利なので洞うと云ふ事は無い。
好い事も悪い事も有る。Elixir (Erlang) はcurry化されてゐないので、arity (引数の個數) の異なる函數は全く区別される。其れをpattern matchに使へる。curry化されるのは、好い事丈ではない。復た見栄えも微妙に成りがちな気がする。だが函數を組み合わせる上では実に有り難い。ただ此れ等微妙さを、乗り越える最高にうまい仕掛けが有りそうな気がする。
言語要素を洞う此う言っても言語に就いてなんら解りはしない。固有の言語要素と云ふのは、余程慎重に取り出さなければ考へられない。要素の組み合わせに就いて言ひたいのではない。おそらく思想なのだ。
然し見栄えが最高に悪いな。

-- license: Public Domain

main :: IO ()
main = do
  print $ map mobius [1..10] == [1, -1, -1, 0, -1, 1, -1, 0, 0, 1]
  print $ mobius (3 * 19 * 19 * 23) == 0
  print $ mobius (3 * 19 * 23) == -1
  print $ mobius (3 * 19 * 23 * 151) == 1

mobius :: Int -> Int
mobius 1 = 1
mobius n
  | any (\(_, index) -> index >= 2) factors = 0
  | odd $ length factors                    = -1
  | otherwise                               = 1
  where
    factors = prime_factors n

prime_factors :: Int -> [(Int, Int)]
prime_factors n = prime_factors' n primes

prime_factors' 1 _ = []
prime_factors' n (prime:ps)
  | index == 0 = prime_factors' n ps
  | otherwise  = (prime, index) : prime_factors' n' ps
  where
    index = prime_index n prime
    n' = n `div` prime ^ index

prime_index :: Int -> Int -> Int
prime_index n prime
  | n `rem` prime == 0 = 1 + prime_index (n `div` prime) prime
  | otherwise          = 0

primes :: [Int]
primes = sieve [2 ..]
  where
    sieve (prime:numbers) =
      prime : sieve [n | n <- numbers, n `rem` prime /= 0]

cf. HaskellでMöbius関数を実装した | 無駄と文化 http://mudatobunka.org/2013/07/705
cf. HaskellでMöbius関数を実装する、その前に回り道してた | 無駄と文化 http://mudatobunka.org/2013/07/774
私は此のみついさまから話題を聞いて書いたが、codeは互いに独立した実装である。

ElixirでMöbius函數 (再掲)

前回はいろいろと一緒に実装して、ごちゃごちゃだったので、最小限にして再掲する。遅延listを自前で実装して使ったものだ。
暫くElixirと付き合っていく事にする。

# license: Public Domain

defmodule Mobius do
  @moduledoc """
  """

  @doc ""
  @spec mobius(integer) :: integer
  def mobius 1, do: 1
  def mobius n do
    factors = Prime.prime_factors n
    cond do
      Enum.any? factors, fn {_, n} -> n >= 2 end -> 0
      rem(length(factors), 2) == 1               -> -1
      true                                       -> 1
    end
  end
end

# {{{ Prime
defmodule Prime do
  @moduledoc """
  """

  @doc "Integer factorization."
  @spec prime_factors(integer) :: [{integer, integer}]
  def prime_factors n do
    prime_factors n, [], primes
  end
  @spec prime_factors(integer, [{integer, integer}], [integer | function() :: List]) :: [{integer, integer}]
  defp prime_factors 1, factors, _ do
    Enum.reverse factors
  end
  defp prime_factors n, factors, [prime|xs] do
    [index: index, number: n] = prime_index n, prime
    if index > 0, do: factors = [{prime, index} | factors]
    prime_factors n, factors, xs.()
  end

  @doc "Primes generator using Sieve of Eratosthenes."
  @spec primes() :: [integer | function() :: List]
  def primes do
    primes Sequence.succ(2)
  end
  defp primes [prime|xs] do
    pred = fn n -> rem(n, prime) != 0 end
    xs = Sequence.filter pred, [prime | xs]
    [prime | fn -> primes xs end]
  end

  @spec prime_index(integer, integer) :: [index: integer, number: integer]
  defp prime_index n, prime do
    prime_index n, prime, 0
  end
  defp prime_index(n, prime, acc) when
    rem(n, prime) != 0 do
    [index: acc, number: n]
  end
  defp prime_index n, prime, acc do
    prime_index div(n, prime), prime, acc + 1
  end
end
# }}} Prime

# {{{ Sequence
defmodule Sequence do
  @moduledoc """
  Lazy evaluated sequence.
  [x | funvtion(xs/0)]
  """

  @doc "Lazy filter."
  @spec filter(function(T) :: boolean, [T | function() :: List]) :: [T | function() :: List]
  def filter pred, [], do: []
  def filter pred, [x] do
    if pred.(x), do: [x], else: []
  end
  def filter pred, [x|xs] do
    if pred.(x) do
      [x | fn -> filter pred, xs.() end]
    else
      filter pred, xs.()
    end
  end

  @doc "Lazy list of integers."
  @spec succ() :: [integer | function() :: List]
  def succ do
    succ 0
  end
  @doc "Lazy list of integers that start from n."
  @spec succ(integer) :: [integer | function() :: List]
  def succ n do
    [n | fn -> succ n + 1 end]
  end
end
# }}} Sequence

IO.puts Enum.map(1..10, function(Mobius.mobius/1)) == [1, -1, -1, 0, -1, 1, -1, 0, 0, 1]
IO.puts Mobius.mobius(3 * 19 * 19 * 23) == 0
IO.puts Mobius.mobius(3 * 19 * 23) == -1
IO.puts Mobius.mobius(3 * 19 * 23 * 151) == 1
# vim:set et sw=2 sts=2 ff=unix foldmethod=marker: