haskell - Why won't GHC reduce my type family? -

-

here's untyped lambda calculus terms indexed free variables. i'm using singletons library singleton values of type-level strings.

{-# language datakinds #-} {-# language gadts #-} {-# language polykinds #-} {-# language typefamilies #-} {-# language typeoperators #-} {-# language undecidableinstances #-}  import data.singletons import data.singletons.typelits  data expr (free :: [symbol])     var :: sing -> expr '[a]     lam :: sing -> expr -> expr (remove as)     app :: expr free1 -> expr free2 -> expr (union free1 free2)

a var introduces free variable. lambda abstraction binds variable appears free in body (if there's 1 matches). applications join free variables of 2 parts of expression, removing duplicates (so free variables of x y x , y, while free variables of x x x). wrote out type families:

type family remove x xs     remove x '[] = '[]     remove x (x ': xs) = remove x xs     remove x (y ': xs) = y ': remove x xs  type family union xs ys     union xs ys = nub (xs :++ ys)  type family xs :++ ys     '[] :++ ys = ys     (x ': xs) :++ ys = x ': (xs :++ ys)  type family nub xs     nub xs = nub' '[] xs  type family nub' seen xs     nub' seen '[] = '[]     nub' seen (x ': xs) = if (elem x seen) (nub' seen xs) (nub' (x ': seen) (x ': xs))  type family if c t f     if true t f = t     if false t f = f  type family elem x xs     elem x '[] = false     elem x (x ': xs) = true     elem x (y ': xs) = elem x xs

i tested out @ interactive prompt:

ghci> :t var (sing :: sing "x") var (sing :: sing "x") :: expr '["x"]  -- ghci> :t (lam (sing :: sing "x") (var (sing :: sing "x"))) (lam (sing :: sing "x") (var (sing :: sing "x")))   :: expr (remove "x" '["x"])  -- not

i surprised learn type of identity function \x. x expr (remove "x" '["x"]), not expr '[]. ghc seems unwilling evaluate type family remove. experimented little more , learned it's not problem type family per se - ghc happy reduce in case:

ghci> :t (proxy :: proxy (remove "x" '["x"])) (proxy :: proxy (remove "x" '["x"])) :: proxy '[]

so: why won't ghc reduce remove "x" '["x"] '[] when query type of gadt? in general, when will-or-won't type checker evaluate type family? there heuristics can use avoid being surprised behaviour?

it works. ghc seems lazy.

λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) (lam (proxy :: proxy "x") (var (proxy :: proxy "x")))   :: expr (remove "x" '["x"])  λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '[] (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '[]   :: expr '[]  λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '["x"]  <interactive>:1:2:     couldn't match type ‘'[]’ ‘'["x"]’     expected type: expr '["x"]       actual type: expr (remove "x" '["x"])     in expression:         (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) ::           expr '["x"]

i changed definitions there isn't dependency on singletons library (easier test in ad-hoc):

{-# language typeoperators, datakinds, typefamilies, gadts #-}  import data.proxy import ghc.typelits  type family remove (x :: symbol) (xs :: [symbol])     remove x '[] = '[]     remove x (x ': xs) = remove x xs     remove x (y ': xs) = y ': remove x xs  data expr (free :: [symbol])     var :: knownsymbol => proxy -> expr '[a]     lam :: knownsymbol => proxy -> expr -> expr (remove as) --    app :: expr free1 -> expr free2 -> expr (union free1 free2)

Comments

Post a Comment

Popular posts from this blog

php - Zend Framework / Skeleton-Application / Composer install issue -

-
i trying create zend framework application using skeleton in netbeans. when run composer install, following error message: "c:\php\php.exe" "c:\composer\composer.phar" "--ansi" "--no-interaction" "update" "--dev" using deprecated option "dev". dev packages installed default now. loading composer repositories package information updating dependencies (including require-dev) requirements not resolved installable set of packages. problem 1 - package requires php >=5.5 php version (5.4.42) not satisfy requirement. problem 2 - installation request zendframework/zendframework 2.5.1 -> satisfiable zendframework/zendframework[2.5.1]. - zendframework/zendframework 2.5.1 requires php >=5.5 -> php version (5.4.42) not satisfy requirement. done. apparently, zend framework only needs php 5.3+ contradicts above. need use php 5.4. my composer.json following: { "name": "
Read more

c# - Better 64-bit byte array hash -

-
i need hash algorithm produces 64-bit hash code ( long ) fewer collisions string.gethashcode() , fast (no expensive calls cryptographic functions). here's implementation of fnv still shows 3% of collisions after testing 2 million random strings. need number way lower. void main() { const string chars = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz!#@$%^&*()_+}{\":?><,./;'[]0123456789\\"; const int n = 2000000; var random = new random(); var hashes = new hashset<long>(); int collisions = 0; for(int = 0; < n; i++) { var len = random.next(chars.length); var str = new char[len]; (int j = 0; j < len; j++) { str[j] = chars[random.next(chars.length)]; } var s = new string(str); if(!hashes.add(get64bithash( s ))) collisions++; } console.writeline("collision percentage after " + n + " random strings: " + ((doubl
Read more

python - PyCharm Type error Message -

-
i'm newbie trying out ml/dbn in python (3.4) under pycharm (comm.ed 4.5). following definition def make_thetas(xmin,xmax,n): xs = np.linespace(xmin,xmax,n) widths = (xs[1:] - xs[:-1])/2.0 thetas = xs[:-1] + widths return thetas throws error "class 'tuple' not define ' sub ', '-' operator cannot used on instance" on - operator on third line (widths = ....) ideas on how code running under pycharm - works alright in interactive python window. thx. to all, after g'g lot have found workaround seems work within pycharm. workaround because (even python newbie) expected python not need explicit typecasting, not when using datatypes imported lib such numpy. def make_thetas(xmin,xmax,n): xs = np.array(np.linspace(xmin,xmax,n)) widths = (xs[1:] - xs[:-1])/2.0 thetas = xs[:-1]+ widths return thetas using docstrings type-hinting such below did not work def make_thetas(xmin,xmax,n): "&q
Read more