HaskellでProject Euler #51

List comprehensioが便利だった.ideoneで<0.3secぐらい.

import           Data.List

-- PE #51
main :: IO ()
main = do
  let n = 8
  -- Suffice to check (11 - n) digits for n primes families
  let chars = take (11 - n) "0123456789"
  let primes = 2 : filter isPrime [3, 5 ..]
  let cands =
        [ variants
        | p <- primes
        , let repr = reverse (show p)
        , let idxMax = length repr - 1
        -- Do not alter ones digit
        , let places c = map fst . filter ((== c) . snd) . tail $ zip [0 ..] repr
        , c <- chars
        , idxs <- filter (not . null) $ subsequences (places c)
        , let variants =
                [ num
                | d <- [0 .. 9]
                -- Do not put zero in the first digit
                , d > 0 || maximum idxs < idxMax
                , let num = replaceDigits p idxs d
                , isPrime num
                ]
        ]
  let answer = head . filter ((== n) . length) $ cands
  print answer

isPrime :: Int -> Bool
isPrime q = q >= 2 && all notFactorOfQ (2 : [3, 5 .. s])
    where
      notFactorOfQ = (/= 0) . mod q
      s = ceiling $ sqrt (fromIntegral q :: Double)

replaceDigits :: Int -> [Int] -> Int -> Int
replaceDigits n [] _ = n
replaceDigits n (i:is) d = let
  unit = 10 ^ i
  d0 = (n `mod` (unit * 10)) `div` unit
  n1 = n + unit * (d - d0)
  in replaceDigits n1 is d

HaskellでProject Euler #11

tailsの使い方の勉強になったのでメモ.

tailsが特別便利と言うよりは,Haskellにはfor文とかwhile文などの繰り返し構文がないので,そもそもiterate系全般がありがたいっぽい. 他にData.List特有のiterate系関数としては,subsequences, permutations, nub(重複排除)あたりが使えそうだと思った.

import           Data.List

main = do
    let array = map (map read . words) $ lines input :: [[Int]]
    -- 候補の列挙
    let horiz = concatMap parse4 array
    let vert = concatMap parse4 (transpose array)
    let diag = parseD4 array
    let adiag = parseD4 (reverse array)
    -- 探索
    let answer = maximum . map product $ vert ++ horiz ++ diag ++ adiag
    print answer

-- リスト中の連続する4要素を組にして列挙
parse4 :: [a] -> [[a]]
parse4 xs = let
    ys = map (take 4) (tails xs)
    in takeWhile ((== 4) . length) ys

-- 二重リスト中の対角方向に連続する4要素を組にして列挙
parseD4 :: [[a]] -> [[a]]
parseD4 arr = let
    squares = concatMap (parse4 . transpose) (parse4 arr)
    in map takeD squares

-- 正方行列の対角要素を抜き出す          
takeD :: [[a]] -> [a]
takeD ((x:_):xss) = x : takeD (map tail xss) 
takeD _ = []

input = "\
\ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\
\ 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\
\ 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\
\ 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\
\ 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\
\ 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\
\ 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\
\ 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\
\ 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\
\ 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\
\ 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\
\ 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\
\ 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\
\ 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\
\ 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\
\ 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\
\ 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\
\ 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\
\ 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\
\ 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

理想のプログラミング言語と副作用

副作用

最近思うに,プログラミングの「副作用」という用語は結構ミスリーディングだ.

確かに副作用を持つコードはバグの温床になりやすいと言うしその実感もあるけど,じゃあ副作用なんてやめて全部主作用にしよう,全部引数と戻り値に書いちゃおう,とはならない. それはおそらく,ある程度大きいプログラムになってくるとすべての情報のやり取りを明示的に書くのが面倒だし,読む方も大変だからだ.

その辺「副作用」なら暗黙的に事を済ませられるのでありがたい. つまり,それは薬の副作用と違って,扱いにくいけれど必要なものだ.

PythonHaskell

ところで,オブジェクト指向や関数型といったプログラミングパラダイムは副作用をストレスフリーに扱うための技術とみなすこともできる.

例えば,オブジェクト指向的なPythonでは関数の代わりにメソッドを利用する.このときオブジェクト指向によれば,副作用のスコープを各メソッドの紐付くオブジェクト(self)内に限定しなければならない.こうすることで副作用の及ぶ範囲がコントロールされ,バグの特定が簡単になったりする.

一方,純粋関数型言語と呼ばれるHaskellでは,副作用を明示的に表現する. と言っても,ただ副作用の情報をどこかにベタ書きするのではなく(それでは副作用の暗黙性が失われてしまう),副作用の種類に応じて用意されているモナドを利用する*1.これによって,すべての副作用は暗黙的でありながらコンパイラのチェックを受けることができるので,バグが減る.

こんな観点から眺めると,2つの対立させられがちなパラダイムが目指す共通の方向性が見えてくる気がする.

理想のプログラミング言語

やっと本題に入るわけだが,個人的な理想のプログラミング言語の要件として, ストレスフリーに副作用を扱えること,というのがある. 上に挙げたPythonHaskellは自分が触ったことのある範囲で一位二位を争う好きな言語だが, どちらにしてもまだ惜しいところがあると思う.

HaskellからPythonを見ると,スコープ以外無差別に副作用を扱おうというのはちょっと無謀だし,コードを読む側やドキュメントをメンテするコストもバカにならない.最近はtypingモジュールも導入されて型検査はしやすくなっているが,副作用の型付けにはまだ程遠そうに思われる.

一方で,PythonからHaskellを見ると,モナドという何でもできる型クラスの担当範囲が節操なく,節操ないがゆえに一つのことをやるのに二つ以上の書き方ができてしまう(一番単純には全部IOでいいじゃん的なやり方を許してしまう)ことがHaskellの書き味・読み味にオーバーヘッドを生んでいる気がする*2

おそらく自分はPythonicなコードの書き方が好きだけど,Haskellの純粋さも欲しいという人間なのだ. そんな自分は,頻出モナドを仕様レベルでサポートしてくれるようなプログラミング言語がほしいと思ってしまう.

*1:自分で作ることもできるが,ライブラリ開発者でなければ普通はやらない気がする.

*2:言語仕様のコンパクトさはHaskellの美点の一つなので,コンパクトゆえ書き方に自由度が残るのは仕方のないことでもあると思う.

pythonでcurryワンライナー

pythonを書いていて、急にcurry化したくなったときはこうする:

import functools
curry = lambda n: lambda f: lambda x: (curry(n - 1)(functools.partial(f, x)) if n > 1 else f(x))

そんでもってこう:

@curry(3)
def func(x, y, z):
    return x + y * z

print(func(42)(4)(-5))  # -> 22

Injective Functional Dependency

マルチパラメタクラスの型変数間に一対一の対応関係をもたせたいとする。 このとき、型変数の間に相互にfuncitonal dependency をもたせればよい。

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

-- | this typechecks
class Foo a b | a -> b, b -> a where
  foo :: a
  bar :: b

Haskellの太いほうの矢印について

Haskellには頻出する矢印が2つある(->=>)。 なかでも=>(型制約導入子?)がくせものである。

  • くせものポイント1:数学の「ならば」とは(一見)違う意味を持つ。
  • くせものポイント2:もちろん日本語の「ならば」とも違う意味を持つ。
  • くせものポイント3:Haskellの中でも型クラス宣言と型インスタンス宣言で意味が違う。
  • くせものポイント4:関数宣言の引数側の制約となるか返り値側の制約となるかでも意味が違う。

というわけで、=>の使いかたを今一度整理しよう。

1. 型クラス宣言の=>

class Functor a => Applicative a where ..

意味:Applicative aならばFunctor a(逆方向)である。

2. 型インスタンス宣言の=>

instance (Foldable f, Monoid m) => Summable (f m) where ..

意味:Foldable fかつMonoid mならばSummable (f m)(順方向)である。

3. 関数宣言の=>

引数側に制約がある場合:

shinyArgFunc :: Sparkling a => a -> Int

意味:shinyArgFuncは「Sparklingインスタンス」からIntへの写像である。

返り値側に制約がある場合:

shinyReturnFunc :: Sparkling a => Int -> a

意味:shinyReturnFuncIntから「Sparklingインスタンス」への写像である。

両方に同じ型変数がある場合:

truelyShinyFunc :: Sparkling a => a -> a

意味:truelyShinyFuncは「Sparklingインスタンス」から「Sparklingインスタンス」への写像である。つまり、引数側の規則が優先される。

4. 無制約の型制約について

型制約を入れずに型変数を登場させることは、 無制約の型クラスを導入することと等価である。 従って、上のルール1-3に注意すると、無制約の型変数xから自明な実装が導かれる:

-- とあるクラスの..
class Trivial a where
  trivialThing :: a

-- 自明な無制約インスタンス
instance Trivial x where
  trivialThing = undefined

-- 自明な無制約値
trivialValue :: x
trivialValue = undefined

全ての型に共通する要素がundefinedしか無いことから、 これらの実装はundefined以外にありえない。 このへん、インスタンス宣言における型制約導入と関数の返り値における型制約導入の類似性が滲み出ている。

5. まとめ

  • 型クラス宣言と型インスタンス宣言における型制約は集合論的には意味が逆*1
  • 関数宣言における型制約も場所によって意味が逆転する。
  • 無制約の型制約による対比から、型クラス↔引数、型インスタンス↔返り値の対応が取れる。

*1:この場合の型制約導入子はインスタンスの実装順を表すとも取れる。そう考えると意味は一緒。

Nixパッケージマネージャとproot

背景

  • Nixはバージョン管理に強いパッケージマネージャーのひとつ。同じライブラリの異なるバージョンを共存させたり、環境設定を巻き戻したりすることが得意。
  • 今回は「Nixを使いたいがrootがないので/nixを作成できない」場合に対処する方法についてまとめる。

方法

PRootのセットアップ

tallocライブラリが必要なのでインストールしておく。たとえばLinuxbrewなどから。

cd $workingdir
git clone https://github.com/proot-me/PRoot.git
cd PRoot/src
make
cp proot $binpath 

簡単ですね。

Nixのインストール

/nixの代わりとなるディレクトリを用意してprootでマウント

mkdir $hostdir  # 例えば~/nix-mntなど
proot -b $hostdir:$/nix bash # お好みのシェルでどうぞ

続けてprootシェル内でNixをインストール

curl https://nixos.org/nix/install | sh

以上。私はfishシェルを使っていたので、さらにマウント直後に

fenv source $HOME/.nix-profile/etc/profile.d/nix.sh

を実行するように設定した。


まとめ

  • rootなしでNixをインストールした。
  • nixを触るときはその都度prootする必要がある。

参考文献

https://nixos.org/wiki/How_to_install_nix_in_home_(on_another_distribution)#Building_native_packages