2009-05-15

インストール済みのモジュールを列挙

haskell

メモ

ghc-pkgの出力をパーズするより遥かに速い
ghciで型を見ながら試行錯誤しちゃうとコードが酷いことになりがち…

-- $ ghc --make listmodules.hs -package ghc -hide-package Cabal-1.7.0 -O
import DynFlags
import ParsePkgConf
import Module
import Distribution.InstalledPackageInfo
import Control.Monad
main=join.((fmap(mapM_(mapM_(mapM_(putStrLn.moduleNameString).exposedModules)))).mapM(loadPackageConfig defaultDynFlags))$["/usr/lib64/ghc-6.10.2/package.conf","/home/xxx/.ghc/x86_64-linux-6.10.2/package.conf"]

2009-05-14

mark-current-lineのときのエラーとprocess-candidate

anything emacs elisp

async-processをcandidateにした時にanything-mark-current-lineでエラーが出るので、適当に回避するようにした。
あと、非同期プロセス側で(display . real)の形式で出力してprocess-filter内部でreadしてelispのconsにし、anything-insert-match内で他の候補と一括でput-text-propertyした方がなんとなく軽かったんで、process-filter内で読み込んだ文字を直接加工するフック？を設けてみたのだけどどうだろう。

*** /tmp/anything.orig	Thu May 14 23:26:00 2009
--- /tmp/anything.el	Thu May 14 23:22:43 2009
***************
*** 2343,2349 ****
           (insertion-marker (assoc-default 'insertion-marker process-info))
           (incomplete-line-info (assoc 'incomplete-line process-info))
           (item-count-info (assoc 'item-count process-info))
!          (real-to-display (assoc-default 'real-to-display process-info)))
  
      (with-current-buffer anything-buffer
        (save-excursion
--- 2343,2350 ----
           (insertion-marker (assoc-default 'insertion-marker process-info))
           (incomplete-line-info (assoc 'incomplete-line process-info))
           (item-count-info (assoc 'item-count process-info))
!          (real-to-display (assoc-default 'real-to-display process-info))
!          (proc-cand-transformer (assoc-default 'proc-cand-transformer process-info)))
  
      (with-current-buffer anything-buffer
        (save-excursion
***************
*** 2372,2378 ****
                    
              (pop lines))
  
!           (setq candidates (reverse candidates))
            (dolist (candidate (anything-transform-candidates candidates process-info))
              (anything-insert-match candidate 'insert-before-markers real-to-display)
              (incf (cdr item-count-info))
--- 2373,2381 ----
                    
              (pop lines))
  
!           (setq candidates (nreverse (if (and proc-cand-transformer (functionp proc-cand-transformer))
!                                         (mapcar proc-cand-transformer candidates)
!                                         candidates)))
            (dolist (candidate (anything-transform-candidates candidates process-info))
              (anything-insert-match candidate 'insert-before-markers real-to-display)
              (incf (cdr item-count-info))
***************
*** 2582,2588 ****
        (when (and anything-display-source-at-screen-top (eq unit 'source))
          (set-window-start (selected-window)
                            (save-excursion (forward-line -1) (point))))
!       (anything-mark-current-line))))
  
  
  (defun anything-mark-current-line ()
--- 2585,2592 ----
        (when (and anything-display-source-at-screen-top (eq unit 'source))
          (set-window-start (selected-window)
                            (save-excursion (forward-line -1) (point))))
!       (when (anything-get-previous-header-pos)
!         (anything-mark-current-line)))))
  
  
  (defun anything-mark-current-line ()

2009-05-02

powerset

haskell

import Data.List (inits, tails)

inits1, tails1 :: [a] -> [[a]]
inits1 = tail . inits
tails1 = init . tails

segs1, powerSet :: [a] -> [[a]]
segs1 = tails1 xs >>= inits1
powerSet xs = []: if null xs then [] else segs1 xs

2009-04-27

mapの再発明

scheme

(use util.match)
(use gauche.test)

(define (mymap f . xss)
  (if (or (null? xss) (any null? xss)) '()
      (match-let1
       (ys . yss) xss
       (cons (apply f (cons (car ys) (mymap car yss)))
             (apply mymap f (cdr ys) (mymap cdr yss))))))

(test* "mymap" '(12 15 18)
       (apply mymap + '((1 2 3) (4 5 6) (7 8 9))))

パタンマッチは便利だなぁ.

2009-04-26

■

$\big{\tilde{.}\underline{.}\tilde{.}}$

2009-04-26

CPSでfoldrとfoldlを汎化する

haskell

同様にして
$f\,(...f\,(f\,(f\,e\,x_0)\,x_1)\,x_2)...)\,x_{n-1}$
$\forall~k~\in~N(g_k=flip\,f\,x_k)$ とすると
$g_{n-1}\,(...g_2(g_1(g_0\,e))...)$
$f\,\tilde{.}\,g = g\,.\,f$ とすると
$(g_0\tilde{.}g_1\tilde{.}\,...\,g_{n-1})\,e$
foldrの形にして
$(foldr\,(flip\,(.))\,id\,.\,map\,(flip\,f))\,xs\,e$
foldrとmapを合成する
$foldr\,(flip\,(.)\,.\,flip\,f)\,id\,xs\,e$
とfoldlがfoldrで表現できる

foldl f e xs = foldr (flip (.) . flip f) id xs e

ここで $(flip\,(.)\,\,.\,flip\,f),\,id$ をパラメータにして

cfold f z xs = foldr f z xs

という式を作り、これに $[]$ と $(x:xs)$ を代入して計算すると

cfold f z [] = foldr f z []
{- = {foldr _ a [] = a}
   z
 -}

cfold f z (x:xs) = foldr f z (x:xs)
{- = {foldr}
   f x (foldr f z xs)
   = {cfold f z xs = foldr f z xs}
   f x (cfold f z xs)
 -}

よって

cfold :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)
cfold _ z [] = z
cfold f z (x:xs) = f x (cfold f z xs)

これを使ってfoldrとfoldlが表現できる

foldr :: (a -> b -> b) -> b -> [a] -> [b]
foldr f a xs = cfold ((.) . f) id xs a
foldl :: (b -> a -> b) -> b -> [a] -> [b]
foldl f e xs = cfold (flip (.) . flip f) id xs e

しかし、これを数行の説明の後ぱっと出してくるyaht*1はなかなかキツいと思いました

参考

Introduction to functional Programming Using Haskell

*1:http://en.wikibooks.org/wiki/Haskell/YAHTの4.6

2009-04-25

謎

haskell

$f\,x_0\,(f\,x_1\,(f\,x_2\,...(f\,x_{n-1}\,a)))$
$\forall~k\in~N(g_k = f x_k)$ とすると
$g_0(g_1...(g_{n-1}(a)))$
$(f.g)\,x=f(g\,x)$ より
$(g_0.g_1.\/...g_{n-1})a$
$id\,x=x$ より
$(g_0.g_1.\/...g_{n-1}.id)a$ をfoldrを使って表すと
$foldr\,(.)\,id\,[g_0,g_1,...,g_{n-1}]$
$xs = [x_0,x_1,...,x_{n-1}]$ とすると
$[g_0,g_1,...,g_{n-1}] = map\,f\,xs$
$(foldr\,(.)\,id\,(map\,f\,xs))\,a$
$(foldr\,(.)\,id\,.\,map\,f)\,xs\,a$
$foldr\,f\,a\,.\,map\,g = foldr\,(f\,.\,g)\,a$ から
$(foldr\,((.)\,.\,f)\,id)\,xs\,a$
$foldrc\,f\,c\,xs=foldr\,((.)\,.\,f)\,c\,xs$
ここで $xs = []$ と $xs = (x:xs)$ を代入して計算すると

foldrc f c [] = foldr ((.) . f) c []
-- foldr _ c [] = c
foldrc f c [] = c

-- foldrc f c xs = foldr ((.) . f) c xs と 仮定
foldrc f c (x:xs) = foldr ((.) . f) c (x:xs)
{-
   = {foldr}
   ((.) . f) x (foldr ((.) . f) c xs
   = {仮定}
   ((.) . f) x (foldrc f c xs)
   = {(.)}
   ((.) (f x)) (foldrc f c xs)
   = {(.)}
   f x . foldrc f c xs
-}

ゆえに

foldrc             :: (a -> b -> b) -> (c -> b) -> [a] -> c -> b
foldrc _ c []      = c
foldrc f c (x:xs)  = f x . foldrc f c xs

だからといってどうというものでもないが