Haskellで組合せ最適化(メモ)

SQLで作成したコードに対応するHaskellコードを作成した
あまり、カッコ良く書けていないですが。。。

■巡回セールスマン全探索

import Data.List (maximumBy,minimumBy,permutations)
import Data.Function (on)

-- エッジのデータ型
data Edge = Edge { path :: [Int], name :: String, cost :: Integer } deriving (Show)  

-- 入力データ
nodes = zip [1..] ["Zurich", "London",  "Berlin", "Roma", "Madrid"]
edges = [(Edge [1, 2] "Zurich,London"  476)
        ,(Edge [2, 3] "London,Berlin"  569)
        ,(Edge [3, 1] "Berlin,Zurich"  408)
        ,(Edge [4, 3] "Roma,Berlin"    736)
        ,(Edge [4, 1] "Roma,Zurich"    434)
        ,(Edge [4, 2] "Roma,London"    894)
        ,(Edge [5, 4] "Madrid,Roma"    852)
        ,(Edge [5, 1] "Madrid,Zurich"  774)
        ,(Edge [5, 2] "Madrid,London"  786)
        ,(Edge [5, 3] "Madrid,Berlin"  1154)]

-- 最大・最小
-- minRoot len or maxRoot len
-- minRoot (length nodes) => ([1,3,2,5,4,1],3049)
-- maxRoot (length nodes) => ([1,5,3,4,2,1],4034)
minRoot n = minimumBy (compare `on` snd) (costRoots (enumRoots [1..n])) 
maxRoot n = maximumBy (compare `on` snd) (costRoots (enumRoots [1..n])) 

-- ルート列挙
-- enumRoots [1,2,3] => [[1,2,3,1],[1,3,2,1]]
-- enumRoots [1,2,3,4] => [[1,2,3,4,1],[1,3,2,4,1],[1,3,4,2,1],[1,2,4,3,1],[1,4,2,3,1],[1,4,3,2,1]]
enumRoots (x:xs) = map (\ys -> x:ys ++ [x]) (permutations xs)

-- ラベル付きコスト算出を展開
-- costRoots [[1,2,3,4,1],[1,2,4,3,1]] => [([1,2,3,4,1],2215),([1,2,4,3,1],2514)]
costRoots roots = map costRoot roots

-- ルート(例:[1,2,3,4,1])のラベル付きコスト算出
-- costRoot [1,2,3,4,1] => ([1,2,3,4,1],2215)
costRoot rt = (rt, sumRoot rt)

-- アトム化したルート(例:[[1,2],[2,3][3,4][4,1]])のコスト算出
-- sumRoot [1,2,3,4,1] => 2215
sumRoot rt = foldl (\acc pt -> acc + (atomCost pt)) 0 (atomRoot rt)

--パス(例:[2,3])のコスト算出
-- atomCost [2,3] => 569
atomCost pt = cost (findEdge pt)

-- パスからエッジを取得
-- formalPath [3, 2] => [2, 3]
-- formalPath [2, 3] => [2, 3]
-- findEdge [2,3] => Edge {path = [2,3], name = "London,Berlin", cost = 569}
formalPath [a, b] = if a < b then [a, b] else [b, a]
findEdge pt = head (filter (\e -> formalPath (path e) == formalPath pt) edges)

-- ルート(例:[1,2,3,1])をパス(例:[1,2])に分解
-- atomRoot [1,2,3,1] => [[1,2],[2,3],[3,1]]
atomRoot (a:b:as) = [a,b] : atomRoot (b:as)
atomRoot as = []

SQLで組合せ最適化(メモ)

http://sqlzoo.net/wiki/SELECT_from_BBC_Tutorial
上記のSQL SERVERで試した

自然数列挙

WITH
  Input(iStart, iEnd) AS (SELECT 1, 10)
, NaturalNumber(n) AS (
    SELECT iStart FROM Input
    UNION ALL
    SELECT n + 1 FROM NaturalNumber INNER JOIN Input
           ON NaturalNumber.n + 1 <= Input.iEnd
  )
SELECT n FROM NaturalNumber ORDER BY n


■全パターン列挙
 順列・組合せ、ではなく、1ノードからnノードの組まで列挙

WITH
  Input(iStart, iEnd) AS (SELECT 1, 8)
, NaturalNumber(n) AS (
    SELECT iStart FROM Input
    UNION ALL
    SELECT n + 1 FROM NaturalNumber INNER JOIN Input
           ON NaturalNumber.n + 1 <= Input.iEnd
  )
, Enum(id, idList) AS (
      SELECT n, CAST(n AS VARCHAR(MAX)) FROM NaturalNumber
      UNION ALL
      SELECT b.n, CAST(a.idList + ',' + CAST(b.n AS VARCHAR(MAX)) AS VARCHAR(MAX))
      FROM Enum a JOIN NaturalNumber b ON a.id < b.n
  )
SELECT * FROM Enum ORDER BY len(idList), idList


■巡回セールスマン全探索

WITH
  Nodes(n, name) AS (
     SELECT 1, 'チューリッヒ' UNION ALL
     SELECT 2, 'ロンドン' UNION ALL
     SELECT 3, 'ベルリン' UNION ALL
     SELECT 4, 'ローマ' UNION ALL
     SELECT 5, 'マドリッド'
 )
, Edges(path, eg, cost) AS (
     SELECT '1,2', 'チューリッヒ,ロンドン', 476 UNION ALL
     SELECT '2,1', 'ロンドン,チューリッヒ', 476 UNION ALL
     SELECT '2,3', 'ロンドン,ベルリン', 569 UNION ALL
     SELECT '3,2', 'ベルリン,ロンドン', 569 UNION ALL
     SELECT '3,1', 'ベルリン,チューリッヒ', 408 UNION ALL
     SELECT '1,3', 'チューリッヒ,ベルリン', 408  UNION ALL
     SELECT '4,3', 'ローマ,ベルリン', 736 UNION ALL
     SELECT '3,4', 'ベルリン,ローマ', 736 UNION ALL
     SELECT '4,1', 'ローマ,チューリッヒ', 434 UNION ALL
     SELECT '1,4', 'チューリッヒ,ローマ', 434 UNION ALL
     SELECT '4,2', 'ローマ,ロンドン', 894 UNION ALL
     SELECT '2,4', 'ロンドン,ローマ', 894 UNION ALL
     SELECT '5,4', 'マドリッド,ローマ', 852 UNION ALL
     SELECT '4,5', 'ローマ,マドリッド', 852 UNION ALL
     SELECT '5,1', 'マドリッド,チューリッヒ', 774 UNION ALL
     SELECT '1,5', 'チューリッヒ,マドリッド', 774 UNION ALL
     SELECT '5,2', 'マドリッド,ロンドン', 784 UNION ALL
     SELECT '2,5', 'ロンドン,マドリッド', 784 UNION ALL
     SELECT '5,3', 'マドリッド,ベルリン', 1154 UNION ALL
     SELECT '3,5', 'ベルリン,マドリッド', 1154
 )
-- pathの組合せ列挙し積上げる
, Head AS (SELECT n, name FROM Nodes WHERE name = 'チューリッヒ')
, Enum(id, idList, pList) AS (
    SELECT n, CAST(n AS VARCHAR(MAX)), CAST(name AS VARCHAR(MAX)) FROM Head
    UNION ALL
    SELECT b.n
              , CAST(a.idList + ',' + CAST(b.n AS VARCHAR(MAX)) AS VARCHAR(MAX))
              , a.pList + ',' + 
                (SELECT SUBSTRING(e.eg, CHARINDEX(',', e.eg)+1, 999)
                 FROM Edges e
                 WHERE e.path = 
                   CAST(a.id AS VARCHAR(MAX)) + ',' + CAST(b.n AS VARCHAR(MAX)))
    FROM Enum a JOIN Nodes b
        ON CHARINDEX(CAST(b.n AS VARCHAR(MAX)), a.idList) = 0
  )
-- 制約・整形
, Domain(idList, pList) AS (
    SELECT idList + ',1', pList + ',{*}'
    FROM Enum 
    WHERE LEN(idList) = LEN('1,2,3,4,5')
      AND CHARINDEX('1', idList) = 1
)
-- Rank
, Rank(idList, pList, cost) AS (
    SELECT c.idList, c.pList, SUM(cost)
    FROM Domain c LEFT JOIN Edges e
        ON CHARINDEX(e.path, c.idList) > 0
    GROUP BY c.idList, c.pList
)
-- 最適化
SELECT * FROM Rank
ORDER BY cost

■ナップザック問題全探索

WITH goods AS (
  SELECT 1 id, 7 val,10 kg UNION ALL
  SELECT 2 id, 2 val, 4 kg UNION ALL
  SELECT 3 id, 9 val, 5 kg UNION ALL
  SELECT 4 id, 4 val, 1 kg UNION ALL
  SELECT 5 id, 9 val, 7 kg UNION ALL
  SELECT 6 id, 7 val, 3 kg UNION ALL
  SELECT 7 id, 4 val, 6 kg UNION ALL
  SELECT 8 id, 5 val, 3 kg
)
,rec(id,idList,sumVal,SumKg) as
  -- 最初の種はid:1からid:8まで
 (SELECT id, CAST(id AS varchar(max)), val, kg FROM goods
  UNION ALL
  -- 種に対して、idが上の(大きい)レコードを積上げる(重複排除)
  SELECT b.id, CAST(a.idList + ',' + CAST(b.id AS varchar(max)) AS varchar(max))
       , a.sumVal+b.val
       , a.SumKg+b.kg
  FROM rec a JOIN goods b ON a.id < b.id
  -- 制約条件
  WHERE a.SumKg+b.kg <= 20
)
,tmp AS
 (SELECT id, idList, sumVal, sumKg
       , max(sumVal) over() AS maxSumVal FROM rec)
SELECT id, idList, sumVal, sumKg, maxSumVal
FROM tmp
--ORDER BY LEN(idList), idList
-- 目的関数
WHERE sumVal = maxSumVal

■最小木問題
 クラスカル法では、素集合データ構造を使用して閉路が
 無いことを確認するが、SQLなので、グローバル変数
 導入するのに、スクリプトを導入することになる。
 それでは、本末転倒なので、怪しい方法をとった。
 これは、正しいか ?

WITH
  Nodes(n, name) AS (
     SELECT 1, 'アリゲータ' UNION ALL
     SELECT 2, 'ブル' UNION ALL
     SELECT 3, 'ホワイトベア' UNION ALL
     SELECT 4, 'シャーク' UNION ALL
     SELECT 5, 'コンドル'
 )
, Edges(path, eg, cost) AS (
     SELECT '1,2', 'アリゲータ,ブル', 1 UNION ALL
     SELECT '1,3', 'アリゲータ,ホワイトベア', 2 UNION ALL 
     SELECT '2,3', 'ブル,ホワイトベア', 1 UNION ALL
     SELECT '2,4', 'ブル,シャーク', 3 UNION ALL
     SELECT '3,4', 'ホワイトベア,シャーク', 5 UNION ALL
     SELECT '3,5', 'ホワイトベア,コンドル', 3 UNION ALL
     SELECT '4,5', 'シャーク,コンドル', 5
 )
, Edges2 AS (
     SELECT ROW_NUMBER() OVER(ORDER BY cost, path) AS id
               , SUBSTRING(e.path, 1, CHARINDEX(',', e.path)-1) AS head
               , SUBSTRING(e.path, CHARINDEX(',', e.path)+1, 999) AS tail
               , e.*
     FROM Edges e
)
-- 種を元にSTEP毎に、最初コストの辺を付与して積上げる
, Enum(prev, idList, step) AS (
    SELECT n, CAST('' AS VARCHAR(MAX)), 1 FROM Nodes
    UNION ALL
    SELECT
           a.prev
         , CASE WHEN CAST(a.prev AS VARCHAR(MAX)) IN (e.head, e.tail)
                      AND LEN(a.idList) = 0
              THEN e.path ELSE a.idList END
         , a.step + 1
    FROM Enum a JOIN Edges2 e
      ON a.step = e.id
  )
, IDCount AS (
    SELECT step, COUNT(*) AS cnt
    FROM Enum
    WHERE 1 < step
    GROUP BY step, LEN(idList)
)
-- 最適化
, TopID AS (
    SELECT TOP 1 step, COUNT(*) AS cnt
    FROM IDCount
    GROUP BY step
    HAVING COUNT(*) = 1
)
, MinPath AS (
    SELECT DISTINCT en.step, en.idList 
    FROM Enum en
    JOIN TopID t
      ON en.step = t.step
)
SELECT m.*, e.eg, e.cost
FROM MinPath m
JOIN Edges e
  ON e.path = m.idList 
ORDER BY m.idList

上記は、postgreSQLなら文字列分割、文字列配列の連結が
可能なので、下記方法で正しく、閉路を確認できるかも ?

WITH
  Split AS (SELECT * FROM regexp_split_to_table('1,2,3#4,5,6', '#') a)
, amp AS (
  SELECT *
  FROM Split a
  LEFT JOIN regexp_split_to_table('3,2', ',') b
    ON strpos(a, b) > 0
)
-- ルートが木の連結でない場合は、差が出る
SELECT (SELECT COUNT(*) FROM Amp) - (SELECT COUNT(*) FROM Split) AS diff

一応postgreSQLで、できたけど
こんなSQLでは、きびしい
動けば良いってもんでは無い

WITH RECURSIVE
  Nodes(n, name) AS (
     SELECT 1, 'アリゲータ' UNION ALL
     SELECT 2, 'ブル' UNION ALL
     SELECT 3, 'ホワイトベア' UNION ALL
     SELECT 4, 'シャーク' UNION ALL
     SELECT 5, 'コンドル'
 )
, Edges(path, eg, cost) AS (
     SELECT '1,2', 'アリゲータ,ブル', 1 UNION ALL
     SELECT '1,3', 'アリゲータ,ホワイトベア', 2 UNION ALL 
     SELECT '2,3', 'ブル,ホワイトベア', 1 UNION ALL
     SELECT '2,4', 'ブル,シャーク', 3 UNION ALL
     SELECT '3,4', 'ホワイトベア,シャーク', 5 UNION ALL
     SELECT '3,5', 'ホワイトベア,コンドル', 3 UNION ALL
     SELECT '4,5', 'シャーク,コンドル', 5
 )
 , Edges2 AS (
     SELECT ROW_NUMBER() OVER (ORDER BY cost) as no
          , SUBSTRING(e.path, 1, strpos(',', e.path)+1) AS head
          , SUBSTRING(e.path, strpos(',', e.path)+3, 999) AS tail
          , e.*
     FROM Edges e
)
-- 例) '1#2#3#4#5'
, FirstStep(trees) AS (SELECT array_to_string(ARRAY(select n from nodes), '#'))
-- 種を元にSTEP毎に、最初コストの辺を付与して積上げる
, Enum(prev, idList, trees, step, state) AS (
    SELECT n, '', (SELECT trees FROM FirstStep), 1, '#' FROM Nodes
    UNION ALL
    SELECT prev
         , CASE WHEN prev IN (CAST(head AS INTEGER), CAST(tail AS INTEGER))
                 AND LENGTH(idList) = 0 AND diff = 0
              THEN path ELSE idList END
           AS idList
         , CASE WHEN diff > 0
            THEN 'NOFIX' || head || ',' || tail ||'#' || trees 
            ELSE CASE
                   WHEN STRPOS(trees, '#' || maxTree) > 0 
                     THEN REPLACE(REPLACE(trees, mixTree, mixTree || ',' || maxTree), '#' || maxTree, '')
                   WHEN STRPOS(trees, maxTree || '#') > 0
                     THEN REPLACE(REPLACE(trees, mixTree, mixTree || ',' || maxTree), maxTree || '#', '')
                   ELSE trees END
           END AS trees
         , step + 1 AS step
         , TO_CHAR(diff, '999')
    FROM 
    (SELECT T1.*
          , TO_NUMBER(diffMaxMin[1], '999') AS diff
          , diffMaxMin[2] AS mixTree
          , diffMaxMin[3] AS maxTree
     FROM
       (SELECT 
           a.prev
         , e.head
         , e.tail
         , a.idList
         , a.trees
         , e.path
         , a.step
         , (SELECT ARRAY[TO_CHAR(diff, '999'), mixTree, maxTree]
            FROM
            (WITH 
               Split AS (SELECT * FROM regexp_split_to_table(a.trees, '#') tree)
             , Amp AS (
                SELECT *
                FROM Split TS
                LEFT JOIN UNNEST(ARRAY[e.head, e.tail]) ht
                ON strpos(TS.tree, ht) > 0
               )
               -- ルートが木の連結でない場合は、差が出る
               SELECT (SELECT COUNT(*) FROM Amp) - (SELECT COUNT(*) FROM Split) AS diff
                    , (SELECT min(tree) FROM AMP WHERE ht is not null) AS mixTree
                    , (SELECT MAX(tree) FROM AMP WHERE ht is not null) AS maxTree
            ) EndWith)
           AS diffMaxMin
        FROM Enum a JOIN Edges2 e
          ON a.step = e.no
       ) T1
     ) T2
  )
, IDCount AS (
    SELECT step, COUNT(*) AS cnt
    FROM Enum
    WHERE 1 < step
    GROUP BY step, LENGTH(idList)
)
-- 最適化
, TopID AS (
    SELECT step, COUNT(*) AS cnt
    FROM IDCount
    GROUP BY step
    HAVING COUNT(*) = 1
    LIMIT 1
)
, MinPath AS (
    SELECT DISTINCT en.step, en.idList 
    FROM Enum en
    JOIN TopID t
      ON en.step = t.step
)
SELECT m.*, e.eg, e.cost
FROM MinPath m
JOIN Edges e
  ON e.path = m.idList 
ORDER BY m.idList


配列ONLYにして、整理した
だいぶ解りやすくなったと思う。

WITH RECURSIVE
  Nodes(n, name) AS (
     SELECT 1, 'アリゲータ' UNION ALL
     SELECT 2, 'ブル' UNION ALL
     SELECT 3, 'ホワイトベア' UNION ALL
     SELECT 4, 'シャーク' UNION ALL
     SELECT 5, 'コンドル'
 )
, Edges(path, eg, cost) AS (
     SELECT '1,2', 'アリゲータ,ブル', 1 UNION ALL
     SELECT '1,3', 'アリゲータ,ホワイトベア', 2 UNION ALL 
     SELECT '2,3', 'ブル,ホワイトベア', 1 UNION ALL
     SELECT '2,4', 'ブル,シャーク', 3 UNION ALL
     SELECT '3,4', 'ホワイトベア,シャーク', 5 UNION ALL
     SELECT '3,5', 'ホワイトベア,コンドル', 3 UNION ALL
     SELECT '4,5', 'シャーク,コンドル', 5
 )
 , Edges2 AS (
     SELECT ROW_NUMBER() OVER (ORDER BY cost) as no
          , SUBSTRING(e.path, 1, strpos(',', e.path)+1) AS head
          , SUBSTRING(e.path, strpos(',', e.path)+3, 999) AS tail
          , e.*
     FROM Edges e
)
-- 例)  ['1', '2', '3', '4', '5'] 単ノードの木のリスト
, FirstStep(trees) AS (SELECT ARRAY(select n::text from nodes))
, Enum(prev, idList, trees, step, minTree, maxTree) AS (
    -- 基底
    -- Nodesを元種にする
    SELECT n, '', (SELECT trees FROM FirstStep), 1, 'minTree', 'maxTree' FROM Nodes
    UNION ALL
    -- 再帰部
    -- STEP毎に、最初コストの辺を付与して積上げる
    SELECT prev
         -- 初回のminTree <> maxTreeの場合のみ、idListを充足
         , CASE WHEN prev IN (CAST(head AS INTEGER), CAST(tail AS INTEGER))
                 AND LENGTH(idList) = 0 AND minTree <> maxTree
              THEN path ELSE idList END
           AS idList
         -- 2つの木の間の連結の場合のみ、木を連結
         , CASE WHEN minTree = maxTree
            THEN trees 
            ELSE
                -- 2つの木を連結
                ARRAY_REMOVE(
                  ARRAY_REPLACE(trees, minTree, minTree || ',' || maxTree)
                , maxTree)
           END AS trees
         , step + 1 AS step
         , minTree
         , maxTree
    FROM 
    (SELECT T1.*
          , minMax[1] AS minTree
          , minMax[2] AS maxTree
     FROM
       (SELECT 
           enm.prev
         , edg.head
         , edg.tail
         , enm.idList
         , enm.trees
         , edg.path
         , enm.step
         -- ルート(edg.head, edg.tail)が2つの木の間の連結でない場合は、MIN(tr) = MAX(tr)
         , (SELECT ARRAY[MIN(tr), MAX(tr)]
            FROM UNNEST(enm.trees) tr
             JOIN UNNEST(ARRAY[edg.head, edg.tail]) node
               ON node = ANY(string_to_array(tr, ',')))
           AS minMax
        FROM Enum enm JOIN Edges2 edg
          ON enm.step = edg.no
       ) T1
    ) T2
  )
-- 最適化
, MinPath AS (
    SELECT DISTINCT en.step, en.idList 
    FROM Enum en
    WHERE en.step = (
        SELECT step
        FROM Enum
        WHERE ARRAY_LENGTH(trees, 1) = 1
        ORDER BY step
        LIMIT 1
    )
)
SELECT m.*, e.eg, e.cost
FROM MinPath m
JOIN Edges e
  ON e.path = m.idList 
ORDER BY m.idList

■巡回セールスマン全探索
 出来損ない

WITH
  Input(iStart, iEnd) AS (SELECT 1, 5)
, Edges(path, eg, cost) AS (
     SELECT '1,2', 'チューリッヒ,ロンドン', 476 UNION ALL
     SELECT '2,1', 'ロンドン,チューリッヒ', 476 UNION ALL
     SELECT '2,3', 'ロンドン,ベルリン', 569 UNION ALL
     SELECT '3,2', 'ベルリン,ロンドン', 569 UNION ALL
     SELECT '3,1', 'ベルリン,チューリッヒ', 408 UNION ALL
     SELECT '1,3', 'チューリッヒ,ベルリン', 408  UNION ALL
     SELECT '4,3', 'ローマ,ベルリン', 736 UNION ALL
     SELECT '3,4', 'ベルリン,ローマ', 736 UNION ALL
     SELECT '4,1', 'ローマ,チューリッヒ', 434 UNION ALL
     SELECT '1,4', 'チューリッヒ,ローマ', 434 UNION ALL
     SELECT '4,2', 'ローマ,ロンドン', 894 UNION ALL
     SELECT '2,4', 'ロンドン,ローマ', 894 UNION ALL
     SELECT '5,4', 'マドリッド,ローマ', 852 UNION ALL
     SELECT '4,5', 'ローマ,マドリッド', 852 UNION ALL
     SELECT '5,1', 'マドリッド,チューリッヒ', 774 UNION ALL
     SELECT '1,5', 'チューリッヒ,マドリッド', 774 UNION ALL
     SELECT '5,2', 'マドリッド,ロンドン', 784 UNION ALL
     SELECT '2,5', 'ロンドン,マドリッド', 784 UNION ALL
     SELECT '5,3', 'マドリッド,ベルリン', 1154 UNION ALL
     SELECT '3,5', 'ベルリン,マドリッド', 1154
 )
, NaturalNumber(n) AS (
    SELECT iStart FROM Input
    UNION ALL
    SELECT n + 1 FROM NaturalNumber INNER JOIN Input
           ON NaturalNumber.n + 1 <= Input.iEnd
)
, Enum(id, idList, pList) AS (
    SELECT n, CAST(n AS VARCHAR(MAX)), CAST('チューリッヒ' AS VARCHAR(MAX)) FROM NaturalNumber
    UNION ALL
    SELECT b.n
              , CAST(a.idList + ',' + CAST(b.n AS VARCHAR(MAX)) AS VARCHAR(MAX))
              , a.pList + ',' + 
                (SELECT SUBSTRING(e.eg, CHARINDEX(',', e.eg)+1, 999)
                 FROM Edges e
                 WHERE e.path = 
                   CAST(a.id AS VARCHAR(MAX)) + ',' + CAST(b.n AS VARCHAR(MAX)))
    FROM Enum a JOIN NaturalNumber b
        ON CHARINDEX(CAST(b.n AS VARCHAR(MAX)), a.idList) = 0
  )
, Domain(idList, pList) AS (
    SELECT idList + ',1', pList + ',{*}'
    FROM Enum 
    WHERE LEN(idList) = LEN('1,2,3,4,5')
      AND CHARINDEX('1', idList) = 1
)
SELECT c.idList, c.pList, SUM(cost) AS cost
FROM Domain c LEFT JOIN Edges e
    ON CHARINDEX(e.path, c.idList) > 0
GROUP BY c.idList, c.pList
ORDER BY SUM(cost)

■列挙
 ノード数決め打ちなら、JOINでつなぐ

WITH Nodes(id, name) AS (
 SELECT 1, '一郎' UNION ALL
 SELECT 2, '二郎' UNION ALL
 SELECT 3, '三郎' UNION ALL
 SELECT 4, '四郎' UNION ALL
 SELECT 5, '四郎'
)
SELECT t1.name A,t2.name B
FROM Nodes t1 JOIN Nodes t2
   ON  t1.id < t2.id
ORDER BY t1.id, t2.id

個人的メモ

http://d.hatena.ne.jp/takeda25/20120511/1336746314
コメント欄
私はATOKをメインに、必要に応じてGoogleIMEを適時素早く切り替えて使うというやり方でタイプしています
テレビ番組名やキャラクター名などの変換はGoogleIMEは圧倒的ですからね
しかしATOKを手放すことは出来ません
慣れの問題もあるのでしょうが、やはり誤字脱字の修正、候補単語の精度でまだ足りないと思います
詳しくはありませんが、そういう調整はとても細かい配慮の積み重ねになるのでは無いでしょうか
そういった配慮がどれだけ出来るかは、結局機械ではなく人間の意識の高さだけだと思います
そこに無料ソフトである壁がある気がします、無料なのに開発には手間ばかりかかりますからね

その2
googleIME使ってますが良いものでは無いですね、固有名詞に強いだけで。
変換自体、特に文自体の変換はイマイチな感じ。

その3
アルゴリズム改良して、究極的には人間の代わりをさせたいGoogleと、
アルゴリズムと人間の知見の両方を使っていきたいブログ主の考えの違いですね。

http://d.hatena.ne.jp/takeda25/20161112/1478956128
Google翻訳がよくなったことは確かだ。
ものすごくよくなっている
それについては各所で書かれている/今後も書かれると思う。
しかし、ぼくが言いたいのは、人間と同じように考えられる機械ができるまでは、人間の補助を必要としない機械翻訳はできない

「父は、母が誕生日を忘れたので、怒っている。」
→"My father is angry because my mother forgot her birthday."
✕her birthday
○his birthday

父母入れ替えると、正しく訳出される
「母は、父が誕生日を忘れたので、怒っている。」
→"My mother is angry because my father forgot her birthday."

コメント
父は、母が誕生日を忘れたので、怒っている。
「この情報だけ」だと、どっちがどっちかわからないでしょ?
でも翻訳の結果は返さないといけない

http://lifehacking.jp/2016/11/google-translate-and-productivity/
Here is a scene from that volume. Standing by a window, behind shutters, the narrator daydreams about a bee buzzing near an eager flower, its stamens “spontaneously curved so that the insect might more easily receive their offering.” Now his focus shifts to the tryst unfolding below, between Charlus (also known as Palamède de Guermantes) and the Guermanteses’ ex-tailor, Jupien, who is younger and of a lower class. The narrator describes how each man was transformed once he was sure no one was watching him.
そのボリュームのシーンがあります。 シャッターの後ろの窓に立って、ナレーターは熱心な花の近くで蜂が鳴っているのを見て、その雄しべは「自発的に湾曲して昆虫がより簡単に奉仕を受けられるようになる」と話しました。 Palamèdede Guermantesとしても知られています)とGuermantesesの元祖、Jupienは、より若く、より低い階級です。 ナレーターは誰も彼を見ていないと確信した後、どのように各人が変容したかを説明します。

なるほど、完璧というわけにはいかないのですが、ちょっと驚いたのは最後の行で “once he was sure no one was watching him” と付け足された部分を、日本語においては適切に文章の中心部分にもってきて「誰も彼をみていないと確信した後、」と句読点つきで翻訳してくれた点です。
あるいは、途中英語ではない言語が入っている部分は、ちゃんと過剰翻訳することなく英字のままにしてあるのもしびれます。

ニューラルネットワークは、文章をたんにフレーズの断片ではなく、意味のある連なりとして認識して過去にトレーニングされた文章例に基づいて翻訳をしていますので、こうした意味の通る翻訳を実現できるのでしょう。

Google 辞めました
http://d.hatena.ne.jp/takeda25/20120511/1336746314
最高の調理器具を使って最高の料理を追求できると思っていた。
しかし、思い違いだったのは、会社の目標は「最高の自動調理機械を作ること」だった。何もかもを機械に任せる。得られる食材を自動的に調べさせ、それらを自動的に調理させる。人間は、関わらなければ関わらないほどいい。


使える機械翻訳20種以上 オンライン 翻訳サイト のまとめ
http://lab.planetleaf.com/network/summary-of-online-translation-service.html

フレーズベース
http://www.trans-frontier.com/blog/2016/07/mt-overview-02/

Google機械翻訳の仕組み&できるようになったこと/まだ難しいことについて、社内の機械学習勉強会で説明します
http://www.yasuhisay.info/entry/2016/11/23/000000

http://fromdusktildawn.hatenablog.com/entry/2015/09/27/113757

Stateモナドの例の式のトレース

SEさんは、トレース得意なので
書く必要が無いかもしれませんが
老婆心から。

計算してみると、結構タイヘン。
計算が得意でない人で、初心者ならば
consを3回もしない例で、やった方が良いかも。
こういう計算の支援系はないのかな、自動計算はできなくても
計算ステップの前後でチェックができたり、適用可能な変形の候補を
プログラムの補完機能みたいに、ポップアップで表示するなりできる
ツールは世の中に存在しないのだろうか?
coqは、興味深いけど、ツールの特性に合わせるのがタイヘンだから
この場合の候補には、ならないと思われる。

お題
下記式の簡約のトレース
>run (cons0 "a" Nil >>= cons0 "b" >>= cons0 "c") 0
>→ (Cons "c" (Cons "b" (Cons "a" Nil)),3)

以下トレース実施
(なお、計算順序は、適用の仕方が可笑しくなければ
たぶん、チャーチロッサー性で担保できると思っている)
run (cons0 "a" Nil >>= cons0 "b" >>= cons0 "c") 0
{
  cons0の定義より
  ∵cons0 :: a -> List a -> Monadic (List a)
  cons0 x xs = Monadic $ \cnt -> (Cons x xs, cnt + 1)
}
→run ( (Monadic $ \cnt1 -> (Cons "a" Nil, cnt1 + 1))
  >>= Monadic (\xs -> \cnt2 -> (Cons "b" xs, cnt2 + 1))
   >>= Monadic (\xs -> \cnt3 -> (Cons "c" xs, cnt3 + 1))) 0
→run (Monadic f >>= Monadic g >>= Monadic h) 0
 f:(\cnt0 -> (Cons "a" Nil, cnt0 + 1))
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
{
 モナドのbind(>>=)の定義より「Monadic f >>= Monadic g」を展開すると
 Monadic f >>= g
  = Monadic (\cnt0 ->
    let (result1, cnt1) = f cnt0
     in run (g result1) cnt1)
}
→run (Monadic (\cnt0 -> let (result1, cnt1) = f cnt0
       in run (Monadic g result1) cnt1)

        >>= Monadic h) 0
 f:(\cnt0 -> (Cons "a" Nil, cnt0 + 1))
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→run (Monadic k >>= Monadic h) 0
 k:(\cnt0 ->
   let (result1, cnt1) = f cnt0
    in run (Monadic g result1) cnt1)

{
 モナドの定義を変形した下記を使用して展開すると
 Monadic k >>= (Monadic h)
  = Monadic (\cnt3 ->
        let (result4, cnt4) = k cnt3
         in run ( (Monadic h) result4) cnt4)
}
→run (Monadic (\cnt3 ->
        let (result4, cnt4) = k cnt3
         in run (h result4) cnt4)
) 0
 k:(\cnt0 ->
   let (result1, cnt1) = f cnt0
    in run (Monadic g result1) cnt1)
run (Monadic (\cnt3 ->
  let (result4, cnt4) = ((\cnt0 ->
    let (result1, cnt1) = f cnt0
     in run (Monadic g result1) cnt1)
cnt3)
   in run ( (Monadic h) result4) cnt4)) 0
{
 runの定義より
 run (Monadic func) initCnt = func initCnt
}
→(\cnt3 ->
  let (result4, cnt4) = ( (\cnt0 ->
    let (result1, cnt1) = f cnt0
     in run (Monadic g result1) cnt1) cnt3)
   in run ( (Monadic h) result4) cnt4)) 0
→(\0 ->
  let (result4, cnt4) = ( (\cnt0 ->
    let (result1, cnt1) = f cnt0
     in run (Monadic g result1) cnt1) cnt3)
   in run ( (Monadic h) result4) cnt4))
→let (result4, cnt4) = ( (\cnt0 ->
   let (result1, cnt1) = f cnt0
    in run (Monadic g result1) cnt1) 0)
  in run ( (Monadic h) result4) cnt4)
{
 runの定義より
 run (Monadic func) initCnt = func initCnt
}
→let (result4, cnt4) = ( (\cnt0 ->
   let (result1, cnt1) = f cnt0
    in (g result1) cnt1) 0)
  in run ( (Monadic h) result4) cnt4)
 f:(\cnt0 -> (Cons "a" Nil, cnt0 + 1))
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\cnt0 ->
   let (result1, cnt1) = (\cnt0 -> (Cons "a" Nil, cnt0 + 1)) cnt0
    in (g result1) cnt1) 0)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\cnt0 ->
   let (result1, cnt1) = (Cons "a" Nil, cnt0 + 1)
    in (g result1) cnt1) 0)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\cnt0 ->
   let (result1, cnt1) = (Cons "a" Nil, cnt0 + 1)
    in (g (Cons "a" Nil)) cnt0 + 1) 0)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ((\cnt0 -> g (Cons "a" Nil) cnt0 + 1) 0)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\0 -> g (Cons "a" Nil) cnt0 + 1) 0)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (g (Cons "a" Nil) 0 + 1)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (g (Cons "a" Nil) 1)
  in run ( (Monadic h) result4) cnt4)
 g:(\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1))
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ((\cnt2 -> \xs -> (Cons "b" xs, cnt2 + 1)) (Cons "a" Nil) 1)
  in run ( (Monadic h) result4) cnt4)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\(Cons "a" Nil) -> \1 -> (Cons "b" xs, cnt2 + 1)) (Cons "a" Nil) 1)
  in run ( (Monadic h) result4) cnt4)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = ( (\(Cons "a" Nil) -> \1 -> (Cons "b" (Cons "a" Nil), 1 + 1)) (Cons "a" Nil) 1)
  in run ( (Monadic h) result4) cnt4)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 1 + 1)
  in run ( (Monadic h) result4) cnt4)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in run ( (Monadic h) result4) cnt4)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in run ( (Monadic h) (Cons "b" (Cons "a" Nil))) 2)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
{
 runの定義より
 run (Monadic func) initCnt = func initCnt
}
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in h (Cons "b" (Cons "a" Nil))) 2)
 h:(\cnt3 -> \ys -> (Cons "c" ys, cnt3 + 1))
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in (\cnt3 -> \ys ->
      (Cons "c" ys, cnt3 + 1)))
(Cons "b" (Cons "a" Nil))) 2)
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in (\2 -> \(Cons "b" (Cons "a" Nil))) ->
      (Cons "c" ys, cnt3 + 1))) (Cons "b" (Cons "a" Nil))) 2)
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in (\2 -> \(Cons "b" (Cons "a" Nil))) ->
      (Cons "c" (Cons "b" (Cons "a" Nil))), 2 + 1))) (Cons "b" (Cons "a" Nil))) 2)
→let (result4, cnt4) = (Cons "b" (Cons "a" Nil), 2)
  in
(Cons "c" (Cons "b" (Cons "a" Nil))), 3)))
→(Cons "c" (Cons "b" (Cons "a" Nil))), 3)))


大筋こんな感じ ?

間違いを見つけて後で書き直すかもしれない。
→修正した。たぶんあっている。
以上です。

SQLをパースするライブラリ(本当にただのメモ)

最近JAVASQLをパースするライブラリを探した。
下のスタックオーバーフローのQAでの状況が、その時の状況に近いのでメモを置いている。

(少し愚痴)
 10年くらい前にも、SQLパーサとMDX操作のライブラリが必要となってSQLパーサを、ほとんどスクラッチで書いたこともある。
それは、ひどい出来栄えでは無いと思っているが、今回は、使えるライブラリがあれば、それを使用した方が良いと思い探してみた。

前よりは良い状況で、無くはないが、豊富に見つかる OR 有力なデファクトの様なものがあるという状況ではない。

フレームワークから抜いてくれば良いという考えも浮かぶが、それは、汎用性の点で、フレームワークの構造に特化しすぎているものが多い。
改造するのなら、Antlrで独自実装した方がマシに思える様なものしか見あたらない。
(フレームワーク作者に、内部構造を分かってもらうドキュメントを作るような人はいない様に思えるので、独自に作るのと、トータルコストが変わらないかもしれない。)

上記10年くらい前の状況の時、字句解析後の字句オブジェクト列へのパターンマッチをする為のライブラリも探したが、見当たらなかった。
見つけたのは、方法論として、正規表現文字列に(字句オブジェクト列を)マッピングすれば擬似的に「字句オブジェクト列へのパターンマッチ」を行うライブラリが作れるのではないか ?
という目論見の記事があったと記憶している。

結局その時は、「字句オブジェクト列へのパターンマッチ」の実装を独自に書き、上記パーサや木の操作に使用した。
「字句オブジェクト列へのパターンマッチ」を作成した時の感想を言うと、なにかオートマトンの教科書の説明を実装したようなコードが出来上がり、対称性はあるが、読みやすいのか読みにくいのか判らないコードになった憶えがある。

しかし、なぜ、フレームワークやcommonsのようなライブラリのプロジェクトは、雨後の筍のように生えてくるのに、SQLパーサや、文字でない対象に正規表現風にマッチする用途の様なライブラリは、次々と候補が生まれてこないのだろうか ?

自分が知らないだけの可能性もあるが、下のスタックオーバーフローのQAでも、応えている人が、マッチする答えを持っていないのか、質問とは、ずれた回答ばかりしている。

最後の回答の「org.eclipse.datatools」は、良いのかもしれないが、まだ試していない。
ただ、自分は、今のところJSQLParserの0.9.3を使用するつもり。
ただし、ORACLEのJOINの+表現とかの方言は対応していないとのこと。
(+)OUTER JOINで等式結合では解析が通るが、LIKE結合では通らない。
例)WHERE T1.NUM1(+) LIKE SBSTR(...

自分の気が済むまで、試しながら、汎用性の高いSQLパーサを目指して自作し、使い方のサンプルを、相当レベルで提供できるまで持っていけるならば、それをを公開するのが一番良いのかもしれない。

また、OSSのコードを読めと言われるかもしれないが、フレームワークやライブラリを読む時、結構ガッカリした経験がある。

1例として、所謂2waySQLのフレームワークで、SQLの変数に値をバインドする仕組みに、OGNLを使用していて、INSERT文を実行するのに12msかかるのに対して、SQLの解析・操作部で、144msを要しているのである。
しかも悪いことに、jdbcのbutchExecuteで実行して12msを更に短縮しようという文脈で、バインド値が少しでも変わると、SQLの解析・操作が始まってしまう作りで、それでは、butchExecuteを使わない方が速い or 固定のSQL(これはどんな用途に使うの?)の連続実行のどちらかしか対応しないとなってしまう。

遅いOGNLに関しては、多くの2waySQLフレームワークで使用されているので、絶望的な気持ちになる。

また、OGNLよりも、(10年前に書いた注意深く時間を掛けたわけでもない)自分でスクラッチで書いた汚いパーサの方がずっと速いという不思議な結果がでる ?

世の中には、確実に自分より頭が良い人達が、沢山いるのに、これは、どういう事なのだろうか ?


■SQL parser library for Java - Retrieve the list of table names present in a SQL statement
http://stackoverflow.com/questions/5572793/sql-parser-library-for-java-retrieve-the-list-of-table-names-present-in-a-sql

(質問)
I am looking for a SQL Library that will parse an SQL statement and return some sort of Object representation of the SQL statement.
>SQLライブラリを探しています。それは、SQL文をparseして、SQL文を表現する何かしらのオブジェクトを返すものです。
My main objective is actually to be able to parse the SQL statement and retrieve the list of table names present in the SQL statement 
(including subqueries, joins and unions).
>主な目的は、当にSQL文をparseすることや、SQLステートメントに存在する、テーブル名のリストを取得することを可能にすることです。
I am looking for a free library with a license business friendly (e.g. Apache license). 
>ビジネスに有効な、ライセンスが無料のライブラリを探しています。(例えば、Apache license)
I am looking for a library and not for an SQL Grammar. 
> 特定のSQL文法用ではないライブラリを探しています。
I do not want to build my own parser.
>自分のパーサーを組み立てることを望んている訳ではありません。
The best I could find so far was JSQLParser, and the example they give is actually  close to what I am looking for.
>これまで見つけた中で一番のものは、JSQLParserです。それらが提供するサンプル例は、当に、かなり、探していたものに近いものです。
However it fails parsing too many good queries (DB2 Database) and I'm hoping to find a more reliable library.
>しかしながら、正しいクエリー(DB2データベース)に対して失敗することが多すぎます。もっと信頼性の高いライブラリを見つけたいのです。

(回答1)
I doubt you'll find anything prewritten that you can just use.
>あなたが、当に使える様な、既に書かれたものを見つけられるかどうか、疑わしく思っています。
The problem is that ISO/ANSI SQL is a very complicated grammar - something like more than 600 production rules IIRC.
>ISO/ANSI SQLが、とても厄介な文法である、という問題、つまり600を超えるIIRCの生成ルールの様なものがあります。
Terence Parr's ANTLR parser generator (Java, but can generate parsers in any one of a number of target languages) 
has several SQL grammars available, 
>Terence ParrのANTLRパーサージェネレータ(javaだけど、たくさんの目的言語の任意の1つのパーサーを生成できます)
>には、いくつかの利用可能なSQL文法が存在しています。
including a couple for PL/SQL, one for a SQL Server SELECT statement, one for mySQL, and one for ISO SQL.
>PL/SQLを計算するものを含んでいすし、SQLサーバーのSELECT文用のもの、mySQL用のもの、そしてISOSQL用のものも含んでいます。
No idea how complete/correct/up-to-date they are.
>完全に、それらに、正しく、かつアップデートされたようなものは存在しないのではないでしょうか。
(回答1へのリプライ)	
I don't actually need a complete Object representation of the SQL statement, what I really need is to extract the names of the tables present in the SQL statement.
>完全なSQL文の表現オブジェクトが必要なのではありません。本当にほしいものは、SQL文のテーブル名を抽出すことなのです。
So, as long as I can somehow get that from an existing library and as long as it correctly parses most queries, I would be happy.
>だから、できるだけ、現存するライブラリからなんとか取得し、できだけ多くのクエリが、正常に終了する。そうなれば、ハッピーだねと言うことなのです。
Writing my own parser right now is not an optin as I don't have the time for that
>自分のパーサーを今書くことは、時間がないということから同意できません。
(更にリプライ)
your not gonna be writing your own parser.your gonna be using a preexisting one.
>自分でパーサーを書きたくないなら、既存のものを使うしかない。
YACC is another option.
>YACCは、その他の選択しですが。
antlr will let you write a code snippet to a java file every time it encounters a table element in the query.
>Antlrによって、クエリーのtable要素に当たったすべての時に、javaファイルに、コード片を記述できるようになります。
you will use this generated java file to parse the sql, and if you wrote the code snippet and header / footer correctly in antlr, then you will just have a list of tables.
>SQLをパースするための、この生成されたJAVAファイルを使えば良いし、コード片やヘッダー/フッターをAntlrで正しく記述すれば、テープルのリストを得られますよ。 	 	
i dont see how you can get a list of table names without a complete representation.
>完全な表現無しに、テーブル名のリストを取得する方法はわかりません。
if your queries are really simplistic, then maybe you can just fake it with regular expressions.
>もし、あなたのクエリーが本当にシンプルなら、正規表現で、やっつけることができるかもしれませんが。
(更にリプライのリプライ)
what I meant was that I don't need a very flexible library.
>私が言いたかったことは、汎用性の高いライブラリがほしいと言うことでは無いのです。
As long as it would understand most of my queries (DB2) and would give me the names of the tables present in the query, I would be happy. 
>出来る限り、多くの(DB2の)クエリーを解釈し、クエリーに存在するテーブル名を得る。そしてハッピーになる。

(回答2)
You needn't reinvent the wheel, there is already such a reliable SQL parser library there, (it's commerical, not free),
>車輪の再発明をする必要は無いですよ、既にそのような、信頼性の高いSQLパーサーライブラリがそこにありますよ。(商用で、無料ではありませんが)
and this article shows how to retrieve the list of table names present in the SQL statement (including subqueries, joins and unions) 
>この記事は、どのようにしてSQL文(サブクエリとJOINとUNIONを含む)に存在するテープル名のリストを取得するかを、提示することですね。
that is exactly what you are looking for.
>それは、正しく、あなたの探していたものですよ。
http://www.dpriver.com/blog/list-of-demos-illustrate-how-to-use-general-sql-parser/get-columns-and-tables-in-sql-script/
This SQL parser library supports Oracle, SQL Server, DB2, MySQL, Teradata and ACCESS.
>このSQLパーサーライブラリは、Oracle, SQL Server, DB2, MySQL, Teradata そして ACCESSをサポートしてますよ。

(回答2へのリプライ)
This does exactly what I am looking for.
>これは、本当に求めていたものです。
However, as I said in my question, I can only consider free libraries (although I'm under the impression that's not going to happen :/) as this is just a prototype.
>が、しかし、質問で言っていた様に、無料のライブラリのみしか考慮対象にできません。(とはいえ、何が起こるかわからないと言う感想ですが)これは、まだほんのプロトタイプにすぎないので。
Nonetheless, thank you! It's good to know that at least there's a good commercial library that does exactly what I need, and maybe later I would be allowed to use it.
>それでも、ありがとう。少なくとも、希望のそのものの良い商用ライブラリがあるということが分かったことはよいことで、後日それを使用させてもらうことになるかもしれません。

(回答3)
Old question, but I think this project contains what you need:
>古い質問だが、このプロジェクトはニーズがあると思う。
Data Tools Project - SQL Development Tools
http://www.eclipse.org/datatools/project_sqldevtools/

Here's the documentation for the SQL Query Parser.
http://www.eclipse.org/datatools/project_sqldevtools/sqltools_doc/SQL%20Query%20Parser%20User%20documentation.htm
>ここにSQLパーサーのドキュメントがあるよ。
Also, here's a small sample program.
>また、ここに小さなサンプルを置きます。
I'm no Java programmer so use with care.
>自分は、Javaプログラマーでないから使う時にきおつけてね。

package org.lala;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.util.Iterator;
import java.util.List;

import org.eclipse.datatools.modelbase.sql.query.QuerySelectStatement;
import org.eclipse.datatools.modelbase.sql.query.QueryStatement;
import org.eclipse.datatools.modelbase.sql.query.TableReference;
import org.eclipse.datatools.modelbase.sql.query.ValueExpressionColumn;
import org.eclipse.datatools.modelbase.sql.query.helper.StatementHelper;
import org.eclipse.datatools.sqltools.parsers.sql.SQLParseErrorInfo;
import org.eclipse.datatools.sqltools.parsers.sql.SQLParserException;
import org.eclipse.datatools.sqltools.parsers.sql.SQLParserInternalException;
import org.eclipse.datatools.sqltools.parsers.sql.query.SQLQueryParseResult;
import org.eclipse.datatools.sqltools.parsers.sql.query.SQLQueryParserManager;
import org.eclipse.datatools.sqltools.parsers.sql.query.SQLQueryParserManagerProvider;

public class SQLTest {

    private static String readFile(String path) throws IOException {
        FileInputStream stream = new FileInputStream(new File(path));
        try {
            FileChannel fc = stream.getChannel();
            MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0,
                    fc.size());
            /* Instead of using default, pass in a decoder. */
            return Charset.defaultCharset().decode(bb).toString();
        } finally {
            stream.close();
        }
    }

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        try {
            // Create an instance the Parser Manager
            //  >パーサー管理インスタンスを生成
            // SQLQueryParserManagerProvider.getInstance().getParserManager
            // returns the best compliant SQLQueryParserManager
            // supporting the SQL dialect of the database described by the given
            // database product information. 
            //  >SQLQueryParserManagerProvider.getInstance().getParserManagerが、
            //  >データベース製品情報によって記述されるデータベースのSQL方言を
            //  >サポートする最適なコンパイラのSQLQueryParserManagerを返します。
            // In the code below null is passed for both the database and version
            // in which case a generic parser is returned
            //  >下のコードで、nullは、データベースとバージョンを無視し
            //  >このケースでは、汎用パーサーを返却します。

            SQLQueryParserManager parserManager = SQLQueryParserManagerProvider
                    .getInstance().getParserManager("DB2 UDB", "v9.1");
            // Sample query
            String sql = readFile("c:\\test.sql");
            // Parse
            SQLQueryParseResult parseResult = parserManager.parseQuery(sql);
            // Get the Query Model object from the result
            QueryStatement resultObject = parseResult.getQueryStatement();
            // Get the SQL text
            String parsedSQL = resultObject.getSQL();
            System.out.println(parsedSQL);

            // Here we have the SQL code parsed!
            QuerySelectStatement querySelect = (QuerySelectStatement) parseResult
                    .getSQLStatement();
            List columnExprList = StatementHelper
                    .getEffectiveResultColumns(querySelect);
            Iterator columnIt = columnExprList.iterator();
            while (columnIt.hasNext()) {
                ValueExpressionColumn colExpr = (ValueExpressionColumn) columnIt
                        .next();
                // DataType dataType = colExpr.getDataType();
                System.out.println("effective result column: "
                        + colExpr.getName());// + " with data type: " +
                                                // dataType.getName());
            }
            List tableList = StatementHelper.getTablesForStatement(resultObject);
            // List tableList = StatementHelper.getTablesForStatement(querySelect);
            for (Object obj : tableList) {
                TableReference t = (TableReference) obj;
                System.out.println(t.getName());
            }
        } catch (SQLParserException spe) {
            // handle the syntax error
            System.out.println(spe.getMessage());
            @SuppressWarnings("unchecked")
            List<SQLParseErrorInfo> syntacticErrors = spe.getErrorInfoList();
            Iterator<SQLParseErrorInfo> itr = syntacticErrors.iterator();
            while (itr.hasNext()) {
                SQLParseErrorInfo errorInfo = (SQLParseErrorInfo) itr.next();
                // Example usage of the SQLParseErrorInfo object
                // the error message
                String errorMessage = errorInfo.getParserErrorMessage();
                String expectedText = errorInfo.getExpectedText();
                String errorSourceText = errorInfo.getErrorSourceText();
                // the line numbers of error
                int errorLine = errorInfo.getLineNumberStart();
                int errorColumn = errorInfo.getColumnNumberStart();
                System.err.println("Error in line " + errorLine + ", column "
                        + errorColumn + ": " + expectedText + " "
                        + errorMessage + " " + errorSourceText);
            }
        } catch (SQLParserInternalException spie) {
            // handle the exception
            System.out.println(spie.getMessage());
        }
        System.exit(0);
    }
}

『Scala 関数型デザイン&プログラミング』の『Exercise 3.13』のふりかえり

第5回 関数型プログラミング勉強会で
Scala 関数型デザイン&プログラミング』の『Exercise 3.13』を解いて実例を試した。

この時、なんとなく解いてしまったので、以下のリンクのような疑問が残った。
http://se-info-tech.hatenablog.com/entry/2015/10/04/124454

もう一度、やってみる。
以下、雑文。

定義は下記となる。

def foldRightViaFoldLeft_1[A,B](l:List[A], z:B)(f:(A,B) => B):B =
  foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))) (z)

実行例として次を考える。
・z = 0
・l = [1,2,3]
また、関数id = (b => b)を、下で使用する。

foldRightViaFoldLeft_1([1,2,3], 0)(+)
=> foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))) (0)

ここで、foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))を簡約していく

foldLeftの初項目のアキュムレータ算出結果
  = ( (g,a) => b => g(f(a,b))) )(g = id,  a = 1)
  = ( b => id(1 + b) )
  = ( b => 1 + b )
  = <1+>
ただし、<1+> := x => 1 + x とする略記

foldLeftの第二項目のアキュムレータ算出結果
  = ( (g,a) => b => g(f(a,b))) )(g = <1+>,  a = 2)
  = ( b => <1+>(2 + b) )
  = <1+><2+>
ただし、<2+> := x => 2 + x とする略記
正確に記述すると
  <1+><2+> := (x => (y => 1 + y)(2 + x))
  (x => (y => 1 + y)(2 + x)) = (y => 1 + y) (x => 2 + x)
  {∵ (y => 1 + y)上では、xは自由変数。
      言い換えると、(y => 1 + y)は、xが何になろうと定義(動作仕様)が変わることは無い。}
となる。

foldLeftの第三項目のアキュムレータ算出結果
  = ( (g,a) => b => g(f(a,b))) )(g = <1+><2+>,  a = 3)
  = ( b => <1+><2+>(3 + b) )
  = <1+><2+><3+>
ただし、<3+> := x => 3 + x とする略記
正確に記述すると
  <1+><2+><3+> := (x => (w => w + 1)(y => 2 + y)(3 + x))
自由変数だから
  (x => (y => (w => w + 1)(2 + y))(3 + x)) = (w => w + 1)(y => 2 + y)(x => 3 + x)
となる。

(エレガントさの為に、演算子<n+>を導入したのに自由変数だからの件を書いたのは
 本末転倒のような気もするが、記号操作に慣れていない層が
 もしかしたらメジャー層とも、思えるので、迎合してみた。でもクドイですね。)

以上より、計算すると

foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0)
 = <1+><2+><3+>(0)
 = <1+><2+>(3)
 = <1+>(5)
 = 6

略記せずに記述すると

foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0)
 = (w => w + 1)(y => 2 + y)(x => 3 + x)(0)
 = (w => w + 1)(y => 2 + y)(0 => 3 + x)
 = (w => w + 1)(y => 2 + y)(3 + 0)
 = (w => w + 1)(y => 2 + y)(3)
 = (w => w + 1)(3 => 2 + y)
 = (w => w + 1)(2 + 3)
 = (w => w + 1)(5)
 = (5 => w + 1)
 = (5 + 1)
 = 6

となる。

どうせ、同値なんだから
とっちでも良い気がするけど
階層構造で頑なに記述してみると

foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0)
 = (x => (y => (w => w + 1)(2 + y))(3 + x))(0)
 = (0 => (y => (w => w + 1)(2 + y))(3 + x))
 = (y => (w => w + 1)(2 + y))(3 + 0)
 = (y => (w => w + 1)(2 + y))(3)
 = (3 => (w => w + 1)(2 + y))
 = (w => w + 1)(2 + 3)
 = (w => w + 1)(5)
 = (5 => w + 1)
 = (5 + 1)
 = 6

となる。

『SE情報技術研究会 管理者』さん、今度はどうでしょうか ?

下のページの方も、ここの所を書いていますね。
http://myutaro.blogspot.jp/2015/05/p51.html
http://nijojin.hatenadiary.jp/entry/2015/06/13/163814


作者の回答の訳

  /*
  The implementation of `foldRight` in terms of `reverse` and `foldLeft` is a common trick for avoiding stack overflows when implementing a strict `foldRight` function as we've done in this chapter. 
> reverse と foldLeft の観点での foldRightの実装は、この章で行っている様な、正格評価の
> foldRight関数実装時に起こる、stack overflowを避ける時に、良く使う方法である。
(We'll revisit this in a later chapter, when we discuss laziness).
> (後の章の遅延評価の議論で再度取り上げる)
  The other implementations build up a chain of functions which, when called, results in the operations being performed with the correct associativity.
> その他の実装は、関数の連鎖で構築しています。それが呼び出されると、正しい結合規則によって
> 実行される操作を、結果として生じさせます。
We are calling `foldRight` with the `B` type being instantiated to `B => B`, then calling
the built up function with the `z` argument.
> foldRight を呼び、B型(の引数)を、B => B にインスタンス化する。
> そして、z引数で、構築した関数の呼び出している
Try expanding the definitions by substituting equals for equals using a simple example, like `foldLeft(List(1,2,3), 0)(_ + _)` if this isn't clear.
> もし、よくわからないなら、foldLeft(List(1,2,3), 0)(_ + _)の様な簡単な例を用いて
> 同値から同値へ書き換えることによって、定義を展開してみてください
Note these implementations are more of theoretical interest - they aren't stack-safe and won't work for large lists.
> これらの実装は、それらはスタックセーフではなく、大きいリストでは働かないという、
> 理論的な関心のみということではないことに注意してください
  */
  def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(reverse(l), z)((b,a) => f(a,b))

  def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
    foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

関数プログラミング(Rバード・Pワドラー)を見るとfoldl、foldrの定義は下記の通り
(なお、引数の順序はscalaとは違し、本とも記述形式を変えて、中高数学っぽくした。
また、<+>は、丸に+の記号で書きたかったが機種依存文字のようなので、代用として使用した。)

右側畳み込み
 foldr(f, a, [x1,x2,...,xn]) = f(x1,f(x2, (... f(xn, a) ...)))

左側畳み込み
 foldl(f, a, [x1,x2,...,xn]) =  f((...f(f(x1, a),x2)...),xn)

読みやすい形式で書くと(f ≡ <+> で、前置記法から中置記法に変更)

 foldr(<+>, a, [x1,x2,...,xn]) = x1 <+> (x2 <+> (x3 <+> (... (xn <+> a) ...)))

 foldl(<+>, a, [x1,x2,...,xn]) = (... ((a <+> x1) <+> x2) ...) <+> xn

となる。
         foldr(<+>, a, []) = a
       foldr(<+>, a, [x1]) = x1 <+> a
    foldr(<+>, a, [x1,x2]) = x1 <+> (x2 <+> a)
 foldr(<+>, a, [x1,x2,x3]) = x1 <+> (x2 <+> (x3 <+> a))

括弧を常に右側にまとめていることから、「右側に畳込む(fold right)」という意味で
この演算をfoldrと呼ぶ。

         foldl(<+>, a, []) = a
       foldl(<+>, a, [x1]) = a <+> x1
    foldr(<+>, a, [x1,x2]) = (a <+> x1) <+> x2
 foldr(<+>, a, [x1,x2,x3]) = ((a <+> x1) <+> x2) <+> x3

同様に、「左側に畳込む(fold left)」という意味で
この演算をfoldlと呼ぶ。


後付の理屈でイメージをまとめて書く

(g,a) => b => g(f(a,b))を使用し、特に、g(f(a,b))でfの後にgを実行することによって

たとえば、上記例では、

『「(a <+> x1) <+> x2」の「(a <+> x1)」の演算<+>を「(...) <+> x2」の演算<+>の後に実行する』

となるように、実行順序を組み替えている。

一般化すると

『「(... <+> x[k-1]) <+> xk」の「(... <+> x[k-1])」の演算<+>を「(...) <+> x[k-1]」の
   演算<+>の後、に実行する』

となるように、実行順序を組み替えている。

なぜなら、gは、現在処理中のlistのheadである、aの左側にあった、リスト要素の演算を行う様に
構成された関数だからである。

変数名の省略を嫌うオブジェクト志向界隈風にかけば、leftsideOparationsという名前で

  def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((leftsideOparations,a) => b => leftsideOparations(f(a,b)))(z)

とするかもしれない。
(ただし、leftsideOparationsの意味は、関数チェーン作成中で、リストl:[a,b,c,d,e,f] の要素cを処理している時に、aとbをcの左側にある要素として、leftsideとし、その操作だからOparationsとした。)

『b => g(f(a,b))』となるのは、その型が B => B つまり、初期値の(b:B) => bと
同じ型である必要があるから理解できる。

『(g,a) => 』は、
(1)このgは、演算の途中結果を蓄積するアキュームレータであり、初期値の(b:B) => bを
   受取る関数型。
(2)aはふつうのfoldと同じで、Listの要素(head)を受取るものだから
  こうなるのは、ふつうに当たり前ですね。

そう考えると、演算の順序を揃えることと、型を合わせることで
『(g,a) => b => g(f(a,b))』に決まってくる様な気がします。

次に

上でやった
  <1+><2+><3+> := (x => (w => w + 1)(y => 2 + y)(3 + x))
  (x => (w => w + 1)(y => 2 + y)(3 + x)) = (w => w + 1)(y => 2 + y)(x => 3 + x)
のように、階層構造で包まずに
 (g,a) => b => g(f(a,b))
を、haskellのcompose演算子を使用して
 (g,a) => g . (b =>f(a,b))
と書く。あるいはscalaの関数を使用して
 (g,a) => g compose (b =>f(a,b))
 (g,a) => (b =>f(a,b)) andThen g
と書けそう。

  def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => g compose (b =>f(a,b)))(z)   // --- (*)

あるいは、

  def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => ((b:B) =>f(a,b)) andThen g)(z)    // --- (**)

(*)の様に書けば、leftsideOparationsなどと書かなくても直感的になにをやっているのか
分りやすいのではないか。
冗長に書くと、小学生でもわかる風な、書き方になるかな ?

  def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((leftsideOparations,a) => 
                              ((b:B) =>f(a,b)) andThen leftsideOparations)(z)

なお、(*)と(**)は、手元にscala実行環境が無いので確認していない。
後で確認して、この記述を残すか、削除するか決める。
(=>確認して動いた。ただ、bに型指定を追加する必要があった。)

この関数の連鎖で構築する方針の答えは、5章の遅延評価の議論への伏線で上げているのかな ?
reverseでの実装と、操作の回数は同じようだが、優劣はどうか ?

対比
  reverseの操作 <=> 関数チェーンの構築
  foldの実行    <=> 関数チェーンの簡約操作

個々の処理
  reverseの操作          : 結果として操作の対象列ができる
  関数チェーンの構築     : 操作の連鎖としての関数列ができる
  foldの実行             : 対象列の要素を順次とりながら計算を実行
  関数チェーンの簡約操作 : 最後の1引数関数から引数を与えて、得た返却値を
                           次の1引数関数に引数として与えて行く連鎖を繰返し
                           最終結果を得る。

『foldの実行』より『関数チェーンの簡約操作』の方がコストは低いかもしれない。
(実験してみれば良いかもしれない。)
ただ、普段の実装で、その微々たるコストを気にするレベルの人ならば
関数型言語は使用せずに、命令型言語のC言語などのコンパイル言語を
使用するべきかもしれない。
そのレベルの人ならば、その方が精神衛生上、楽なのでは ?

関数型が有利と言われている、並列処理もコンパイラやフレームワークの最適化に委ねないで
自ら考えた最適解をハードコーディングした方が、頭の良い人ならば
より良い解が求まるような気がする。

(でも、昔からある格言の、最適化は最後までやるな! とか 最適化は絶対するな!(大体は
 物事が見えていない分かっていない人の要らない思い込みで、別の方法が在るはずだから)
 とかありますが !"#$%&'?)

自分は頭が悪いし、このレベルの問題に時間を掛けて他のことができなくなるのは
嫌なので、気にせずに「common trick」と言っていたreverseを使う方針を採用するのが
現時点では、良いと思う。
別にみんなに使われる共通基盤を作る訳ではないし
仮にそうでもアルファバージョン位では、カリカリに最適化しなければいけない
理由もない様な ?

皆様は、どう考えるでしょうか ?