Menu
  • HOME
  • TAGS

How should the general type of a “lemma” function be understood?

Tag: haskell,theorem-proving,dependent-type,higher-rank-types

Perhaps this is a stupid question. Here's a quote from the Hasochism paper:

One approach to resolving this issue is to encode lemmas, given by parameterised equations, as Haskell functions. In general, such lemmas may be encoded as functions of type:

∀ x1 ... xn. Natty x1 → ... → Natty xn → ((l ~ r) ⇒ t) → t

I thought I understood RankNTypes, but I can't make sense of the last part of this proposition. I'm reading it informally as "given a term which requires l ~ r, return that term". I'm sure this interpretation is wrong because it seems to lead to a circularity: we don't know l ~ r until the conclusion of the proof itself, so how can I be expected to provide as an assumption of the proof a term which requires that?

I would have expected an equality proof to have a type more like this:

Natty x1 → ... → Natty xn → l :~: r

Informally, "given a bunch of Nattys, return a proof that the propositions l and r are equal" (using GHC's Data.Type.Equality). This makes far more sense to me, and seems to align with what you'd say in other dependently typed systems. I'm guessing it's equivalent to the version in the paper, but I'm struggling to mentally square away the two versions.

In short, I'm confused. I feel like I'm missing a key insight. How should I read the type ((l ~ r) => t) -> t?

Best How To :

I'm reading it as "given a term which requires l ~ r, return that term"

It's "given a term whose type contains l, return that term with all ls being substituted by rs in the type" (or in the other direction r -> l). It's a very neat trick, that allows you to delegate all cong, trans, subst and similar stuff to GHC.

Here is an example:

{-# LANGUAGE GADTs, DataKinds, PolyKinds, TypeFamilies, TypeOperators, RankNTypes #-}

data Nat = Z | S Nat

data Natty n where
    Zy :: Natty Z
    Sy :: Natty n -> Natty (S n)

data Vec a n where
    Nil  :: Vec a Z
    Cons :: a -> Vec a n -> Vec a (S n)

type family (n :: Nat) :+ (m :: Nat) :: Nat where
    Z     :+ m = m
    (S n) :+ m = S (n :+ m)

assoc :: Natty n -> Natty m -> Natty p -> (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => t) -> t
assoc  Zy     my py t = t
assoc (Sy ny) my py t = assoc ny my py t

coerce :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce ny my py xs = assoc ny my py xs

UPDATE

It's instructive to specialize assoc:

assoc' :: Natty n -> Natty m -> Natty p ->
            (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p)))
                                               -> Vec a (n :+ (m :+ p))
assoc'  Zy     my py t = t
assoc' (Sy ny) my py t = assoc ny my py t

coerce' :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce' ny my py xs = assoc' ny my py xs

Daniel Wagner explained what's going on in comments:

Or, to say it another way, you can read ((l ~ r) => t) -> t as, "given a term that is well typed assuming that l ~ r, return that same term from a context where we have proven l ~ r and discharged that assumption".

Let's elaborate the proving part.

In the assoc' Zy my py t = t case n is equal to Zy and hence we have

((Zy :+ m) :+ p) ~ (Zy :+ (m :+ p))

which reduces to

(m :+ p) ~ (m :+ p)

This is clearly identity and hence we can discharge that assumption and return t.

At each recursive step we maintain the

((n :+ m) :+ p) ~ (n :+ (m :+ p))

equation. So when assoc' (Sy ny) my py t = assoc ny my py t the equation becomes

((Sy n :+ m) :+ p) ~ (Sy n :+ (m :+ p))

which reduces to

 Sy ((n :+ m) :+ p) ~ Sy (n :+ (m :+ p))

due to the definition of (:+). And since constructors are injective

constructors_are_injective :: S n ~ S m => Vec a n -> Vec a m
constructors_are_injective xs = xs

the equation becomes

((n :+ m) :+ p) ~ (n :+ (m :+ p))

and we can call assoc' recursively.

Finally in the call of coerce' these two terms are unified:

 1. ((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p))
 2.                                      Vec a ((n :+ m) :+ p)

Clearly Vec a ((n :+ m) :+ p) is Vec a (n :+ (m :+ p)) under the assumption that ((n :+ m) :+ p) ~ (n :+ (m :+ p)).

Setting id and class with the haskell diagrams package

haskell,svg,haskell-diagrams

This cannot be done currently in diagrams, although it is something we would like to have in the future. You can get part of the way there using the diagrams-canvas backend, but that only displays on a local host and cannot be embedded into a web page. The only thing...

Haskell: `==' is not a (visible) method of class

haskell,compiler-errors,instance,equality,typeclass

It isn't clear what you are trying to achieve. Here are some thoughts: When you declare an instance of a class like instance (Eq a) => PartOrd a, you are expected to provide implementations for the functions in PartOrd a (ie partcmp, not == and \=). The compiler is telling...

Mapping with IO actions in Haskell

list,haskell,io

Here is a function f' which does what you describe. f' :: [(String,String)] -> IO [Bool] f' = mapM $ uncurry f Let me know if something is unclear! And, just to be clear, here is how you run it: main = do res <- f' [("a.txt", "b.txt"), ("c.txt", "d.txt")]...

apply a transformation with function inline

haskell

The read lambda applies to the first argument and the first argument to the function given to foldl is the accumulator. Those two arguments are the opposite for foldr. So, expanded, it looks like this: foldl (\acc element -> (read acc :: Int) + element) 0 ["10", "20", "30"] Since...

attoparsec: succeeding on part of the input instead of failing

haskell,attoparsec

Depending on if consuming the whole input should be the property of parseNoteDocument or just the tests, I'd extend one or the other with endOfInput or atEnd. I'd suggest to define a proper Parser for your documents, like parseNoteDocument' :: Text -> Parsec NoteDocument parseNoteDocument' = many parseLine and then...

Normal probability density function - GSL equivalent in Haskell

haskell,statistics,gsl

Here's an example which uses random-fu: import Data.Random -- for randomness import Text.Printf -- for printf import Data.Foldable -- for the for_ loop -- pdf and cdf are basically “Distribution -> Double -> Double” main = do -- defining normal distribution with mean = 10 and variation = 2 let...

Stopping condition on a recursive function - Haskell

string,function,haskell,if-statement,recursion

Your code doesn't handle the case where a line is shorter than the maximum length. This is somewhat obscured by another bug: n is decremented until a whitespace is found, and then f is called recursively passing this decremented value of n, effectively limiting all subsequent lines to the length...

When will travis-ci support ghc 7.10?

haskell,travis-ci

Using multi-ghc-travis, you can also set up Travis-CI for ghc 7.10 (apart from other versions).

Tokenizer identifier in Haskell

haskell

For the Not in scope: data constructor 'Integer' part, the problem is that you have an extra Integer in the line isDigit c = TNumber Integer (read c) : tokenize cs which should be isDigit c = TNumber (read [c]) : tokenize cs The [c] part is needed because read...

How do I avoid writing this type of Haskell boilerplate code

haskell,boilerplate

I assume that we'd like to have a solution for the general case where the changing type parameter is not necessarily in the right position for DeriveFunctor. We can distinguish two cases. In the simple case out data type is not recursive. Here, prisms are a fitting solution: {-# LANGUAGE...

Hook into GHC runtime system

haskell,functional-programming,runtime,transactional-memory

(# s2#, TVar tvar# #) is an unboxed tuple. The name stg_newTVarzh is built from: The stg_ prefix, which is common to the whole GHC runtime, and stands for the spineless-tagless G-machine, an abstract machine to evaluate functional languages; newTVar which is the first part of newTVar#; the final zh,...

Fold over a heterogeneous, compile time, list

haskell,type-level-computation,hlist

Answering your comment: Actually, I can do if I can filter the heterogeneous list by type. Is that possible? You can filter the heterogeneous list by type if you add a Typeable constraint to b. The main idea is we will use Data.Typeable's cast :: (Typeable a, Typeable b) =>...

Running executable files using Haskell

shell,haskell,command-line-arguments,executable

The documentation for readProcess says: readProcess :: FilePath Filename of the executable (see RawCommand for details) -> [String] any arguments -> String standard input -> IO String stdout When it's asking for standard input it's not asking for a file to read the input from, but the actual contents of...

Why are takeR, dropR and splitAtR missing from Data.Sequence?

haskell,containers,sequence

length is O(1), so splitAt suffices to define everything you need, in an efficient way. splitAtR i s = splitAt (length s - i) s takeR i s = snd $ splitAtR i s dropR i s = fst $ splitAtR i s According to the docs, splitAt costs O(log(min(i,length...

How does Frege generalize number literals?

haskell,frege

Simple decimal literals without type indicator (i.e. one of the letters lndf) do not automatically have type Int in Frege. They will get assigned the type you probably wanted, and the literal will get adapted accordingly. This is why they are called DWIM (do what I mean) literals. This is...

Haskell IO - read from standard input directly to list

haskell

You may write: main = readLn >>= print . subsequences You will need to nail down the type to be read, for example by having a monomorphic subsequences or by annotating readLn. In ghci: Data.List> (readLn :: IO [Integer]) >>= print . subsequences [1,2,3] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] (I typed in the first...

Haskell do clause with multiple monad types

haskell,monads

A do block is for a specific type of monad, you can't just change the type in the middle. You can either transform the action or you can nest it inside the do. Most times transformations will be ready for you. You can, for instance have a nested do that...

Keep track of loop without a counter

haskell

You can certainly do this without changing the type signature of func :: [Int] -> [Int]: have func call a different function, which takes an extra argument that is the counter you were talking about: func :: [Int] -> [Int] func = go 0 where go _ [] = []...

Haskell powerset function - How to avoid Couldn't match expected type `IO t0' with actual type `[[Integer]]'

haskell

the problem is main = ... main should have type IO () but you give an expression with type [[Integer]] (as the compiler tells you) - so as I think you want to output the result to the console I think you are looking for print this works for me:...

Replace all [ ] with {} - as short as possible [on hold]

haskell

All you need is love and to split print into putStrLn . show and then add a simple map in-between which does the conversion: main :: IO () main = let fn '[' = '{' fn ']' = '}' fn c = c in (readLn :: IO [Integer]) >>= putStrLn...

What is haskellng? What is the difference between 'haskellPackages' and 'haskellngPackages'?

haskell,cabal,cabal-install,nix,haskell-ng

Could someone please explain what haskellng is in a simple, clear way? Well, haskellng is the next generation Nix Haskell package set made for Nix. I think most of the work was done by Peter Simons. But note that in the latest master version, haskellngPackages has been renamed back...

First three items of a list in Haskell

haskell

Well, foo (x:y:z:xs) plus a “too short clause” certainly wouldn't be a bad solution. Another would be foo xs = case splitAt 3 xs of ([x,y,z],xs') -> calc x y z : foo (y:z:xs') _ -> [] Or, perhaps nicest, import Data.List (tails) foo xs = [ calc x y...

Get each fibbonacci value in haskell

haskell,fibonacci

Consider the simpler problem of summing the first 100 positive integers: sum [x | x <- [1,2..], x <= 100] This doesn't work either. As a human, you know that once x <= 100 returns False, it will never return True again, because x is getting larger. But Haskell doesn't...

Haskell return lazy string from file IO

haskell,file-io,lazy-evaluation

You're right, this is a pain. Avoid using the old standard file IO module, for this reason – except to simply read an entire file that won't change, as you did; this can be done just fine with readFile. readCsvContents :: Filepath -> IO String readCsvContents fileName = do contents...

logical expression evaluator Haskell

haskell

You're making eval a bit too low-level. By including Literals in the signature. A better way to do this is, is using recursion: eval :: Expression -> Bool eval (Literal x) = x eval (Operation AND x y) = (eval x) && (eval y) eval (Operation OR x y) =...

Decremented value called in the recursion in Haskell

string,function,haskell,recursion,parameters

Yes, once you call again f with a new value of n, it has no way to reference the old value of n unless you pass it explicitly. One way to do it is to have an internal recursive function with its width parameter, as you have, but that can...

Why is lazy evaluation in Haskell “not being lazy”?

haskell,lazy-evaluation

take is of type Int -> [a] -> [a], i.e. it returns a list. It seems you’re looking for head, which returns one element. head $ head $ repeat [1..] ...

Thread blocked indefinitely in an MVar operation

haskell,concurrency,network-programming

Three days later and its solved: Was actually unrelated to either the networking or concurrency code, and infact caused by my incorrect re-implementation of Yampas dpSwitch in Netwire. Corrected code posted below for anyone wishing to implement this function: dpSwitch :: (Monoid e, Applicative m, Monad m, T.Traversable col) =>...

Why doesn't `iterate` from the Prelude tie the knot?

haskell,tying-the-knot

Tying the not like that doesn't appear to increase sharing. Contrast with: cycle xs = let x = xs ++ x in x Tying the knot here has the effect of creating a circular linked list in memory. x is its own tail. There's a real gain. Your suggested implementation...

Combining Event and an attribute in threepenny-gui

haskell,threepenny-gui

This is intentional: The UI.checkedChange event only triggers when the user clicks the checkbox, but not when it is set programmatically. The intention is that the bBool behavior represents the canonical state of the checkbox and the UI.checkedChange event represents request from the user to change it, which may or...

Why is f <$> g <$> x equivalent to (f . g) <$> x although <$> is not right-associative?

haskell,syntax,infix-notation,applicative,infix-operator

Why is f <$> g <$> x equivalent to (f . g) <$> x ...well, this isn't so much a functor-thing as a Haskell-thing. The reason it works is that functions are functors. Both <$> operators work in different functors! f <$> g is in fact the same as...

Isabelle: Unsupported recursive occurrence of a datatype via type constructor “Set.set”

recursion,isabelle,theorem-proving

The theoretical explanation First of all, the notion of a datatype of commands that allow non-deterministic choice from an arbitrary set of commands is deeply problematic. I will explain why. Suppose you had a datatype datatype Cmd = Skip | NonDeterministicChoice "Cmd set" like you wanted. Let A := (UNIV...

Where to store API keys and other 'secrets' in a yesod app

haskell,yesod,api-key

There are many approaches to this, mostly depending on what flavor of devops/hosting your prefer. One option is to put a dummy value in the config file and override it with an environment variable at runtime (see: https://github.com/yesodweb/yesod/wiki/Configuration#overriding-configuration-values-with-environment-variables). You can also having an extra settings file for production that overrides...

How can I express the type of 'takeWhile for vectors'?

haskell,types,binding,dependent-type

The type you suggest can not be implemented, i.e. it is not inhabited: takeWhileVector :: (a -> Bool) -> Vector a n -> Vector a m Remember that the caller chooses the type variables a,n,m. This means that the caller can use your function as e.g. takeWhileVector :: (a ->...

How can I express foldr in terms of foldMap for type-aligned sequences?

haskell,types,monoids,type-variables,foldable

I found that this typechecks: {-# LANGUAGE RankNTypes #-} module FoldableTA where import Control.Category import Prelude hiding (id, (.)) class FoldableTA fm where foldMapTA :: Category h => (forall b c . a b c -> h b c) -> fm a b d -> h b d foldrTA ::...

Best practice for handling data types from 3rd party libraries in Haskell?

haskell,types

I am not ready to give a nice list of best practises, but for starters if you want to keep stuff sanely organized, use explicit exports instead of just exporting everything, e.g: module Parser ( parseConfig ) where ... Explicit exports also allow you to reexport your imports, e.g. module...

Haskell - generate and use the same random list

haskell,random

Here is a simple example (@luqui mentioned) you should be able to generalize to your need: module Main where import Control.Monad (replicateM) import System.Random (randomRIO) main :: IO () main = do randomList <- randomInts 10 (1,6) print randomList let s = myFunUsingRandomList randomList print s myFunUsingRandomList :: [Int] ->...

Can't find defaultTimeLocale in Data.Time.Format

haskell,cabal

For some reason, cabal wasn't using the version I thought it was (1.5) but (1.4) probably from the haskell platform. Uprading fixed the problem.

Instance of Show for Lambda

haskell,lambda,instance,show,typeclass

Add an instance declaration for the Show class. instance Show LExpr where show = show' And remove the deriving(Show) part data LExpr = Variable String -- variable | Apply LExpr LExpr -- function application | Lambda String LExpr -- Lambda abstraction deriving (Eq) ...

Recursion scheme in Haskell for repeatedly breaking datatypes into “head” and “tail” and yielding a structure of results

haskell,recursion

This looks like a special case of a (jargon here but it can help with googling) paramorphism, a generalisation of primitive recursion to all initial algebras. Reimplementing ListCase Let's have a look at how to reimplement your function using such a combinator. First we define the notion of paramorphism: a...

Idiomatic list construction

list,haskell,functional-programming,idiomatic

The multiple call to addPoints could be replaced by a fold. As suggested in a comment, reversing your addPoint function would make things easier: addPoint' :: Point -> Polyline -> Polyline addPoint' p line = p:line So then your constructLine function could build a temporary list of the points to...

Refactor an IO recursive loop into a monad folding in Haskell

sockets,haskell,network-programming,io-monad

The idiomatic way to repeat the same action over and over again forever is forever serverLoop :: Socket -> IO () serverLoop sock = forever $ do (conn, _) <- accept sock forkIO $ handleConn conn ...

How to convert a Rational into a “pretty” String?

haskell,formatting,rational

Here's one that I wrote a few weeks ago. You can specify the number of decimals you want (correctly rounded), or just pass Nothing in which case it will print the full precision, including marking the repeated decimals. module ShowRational where import Data.List(findIndex, splitAt) -- | Convert a 'Rational' to...

Haskell: When declaring a class, how can I use a type variable that is not immediately in the constructors?

haskell

using TypeFamilies The problem is that you somehow have to connect b with your collection (the elements in it) - there are several ways to do this but I think a rather nice one is using TypeFamilies: {-# LANGUAGE TypeFamilies #-} module Test where import qualified Data.Map as Map import...

IO Monad Example

haskell

The code you posted desugars into the following. x >>= (\a -> print a >> return 500) Or, expanding out the definition of (>>) x >>= (\a -> print a >>= (\_ -> return 500)) Then, you can see that in the different calls to (>>=), the types a and...

issues with installing newer cabal version for haskell vim now

ubuntu,haskell,vim,ubuntu-14.04,cabal

Your $PATH variable seems to be broken. In a comment you said it was /home/me/google-cloud-sdk/bin:/.cabal/bin:/usr/local/sbin:/usr/local/bin:/usr/sb‌​in:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games This means that your shell (assumed to be bash) will look in the following directories /home/me/google-cloud-sdk/bin /.cabal/bin /usr/local/sbin /usr/local/bin /usr/sb‌​in /usr/bin /sbin /bin /usr/games /usr/local/games when looking for executable. If you look at the second...

How to “wrap” monadic return value

haskell,monads

createNotificationIdentifierItem :: APNSIdentifier -> APNSItem createNotificationIdentifierItem (Identifier identifier) = Item $ do putWord8 3 putWord16be 4 putWord32be identifier or createNotificationIdentifierItem :: APNSIdentifier -> APNSItem createNotificationIdentifierItem (Identifier identifier) = do Item $ putWord8 3 Item $ putWord16be 4 Item $ putWord32be identifier after making APNSItem an instance of Monad (you can...

Implementing map on a tree using fold

scala,haskell

Try to write your last line as def map(tree:Tree[Int])(f:Int=>Int) : Tree[Int] = fold(tree , EmptyTree:Tree[Int])((l,x,r) => Node(f(x),l,r)) Scala's type inference is very limited compared to haskell, in this case it tries to infere type of fold from it's arguments left to right, and incorectly decides that result type of fold...

Haskell make recipe fails for Paradox theorem prover using GHC

linux,haskell,make,ghc,theorem-proving

Looks like paradox was written for a rather old version of GHC. You can fix all these "Could not find module" errors by using GHC version 7.8 or older and setting GHC = ghc -hide-package base -package haskell98 in the Makefile, though you will likely encounter more errors after that....