Search 250 million research papers

Weak type classes

Michael Ćwikel, Yoram Sagher · Journal of Functional Analysis · 1983

Cited by 7

Implementing type classes

John Peterson, Mark P. Jones · 1993

We describe the implementation of a type checker for the functional programming language Haskell that supports the use of type classes. This extends the type system of ML to support overloading (ad-hoc polymorphism) and can be used to implement features such as equality types and numeric overloading in a simple and general way.

Cited by 61Open access

Beyond Type Classes

Andreas Rossberg, Martin Sulzmann · 2002

We discuss type classes in the context of the Chameleon language, a Haskell-style language where overloading resolution is expressed in terms of the meta-language of Constraint Handling Rules (CHRs). In a first step, we show how to encode Haskell's single-parameter type classes into Chameleon. The encoding works by providing an approrpriate set of CHRs which mimic the Haskell conditions. We also consider constructor classes, multi-parameter type classes and functional dependencies. Chameleon provides a testbed to experiment with new overloading features. We show how some novel features such as universal quantification in context can naturally be expressed in Chameleon.

Cited by 0

Modular Type Classes

Dryer, Derek, Harper, Robert, Chakravarty, Manuel M.T. et al. · KiltHub Repository · 2007

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and ad hoc polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.

Cited by 0Open access

Modular Type Classes

Dryer, Derek, Harper, Robert, Chakravarty, Manuel M.T. et al. · KiltHub Repository · 2007

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and ad hoc polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.

Cited by 0Open access

Total Type Classes

Robert Weingart, Nicolas Wu · 2025

In Haskell, type classes can act like functions from types to terms. However, unlike for functions, there is no way for the programmer to ask the compiler to verify that classes pattern-match exhaustively on their arguments, and their usage must always be marked by a constraint even when they are exhaustive.

Cited by 1Open access

Type Abstractions and Type Classes

Robert Harper · Cambridge University Press eBooks · 2012

An interface is a contract that specifies the rights of a client and the responsibilities of an implementor. Being a specification of behavior, an interface is a type. In principle any type may serve as an interface, but in practice it is usual to structure code into modules consisting of separable and reusable components. An interface specifies the behavior of a module expected by a client and imposed on the implementor. It is the fulcrum on which is balanced the tension between separability and integration. As a rule, a module should have a well-defined behavior that can be understood separately, but it is equally important that it be easy to combine modules to form an integrated whole.

Cited by 0

Type Abstractions and Type Classes

Robert Harper · Cambridge University Press eBooks · 2016

An interface is a contract that specifies the rights of a client and the responsibilities of an implementor. Being a specification of behavior, an interface is a type. In principle, any type may serve as an interface, but in practice it is usual to structure code into modules consisting of separable and reusable components. An interface specifies the behavior of a module expected by a client and imposed on the implementor. It is the fulcrum balancing the tension between separation and integration. As a rule, a module ought to have a welldefined behavior that can be understood separately, but it is equally important that it be easy to combine modules to form an integrated whole.

Cited by 0

Type Reconstruction for Type Classes

Tobias Nipkow, Christian Prehofer · Journal of Functional Programming · 1995

Abstract We study the type inference problem for a system with type classes as in the functional programming language Haskell. Type classes are an extension of ML-style polymorphism with overloading. We generalize Milner's work on polymorphism by introducing a separate context constraining the type variables in a typing judgement. This leads to simple type inference systems and algorithms which closely resemble those for ML. In particular, we present a new unification algorithm which is an extension of syntactic unification with constraint solving. The existence of principal types follows from an analysis of this unification algorithm.

Cited by 45

Type-checking multi-parameter type classes

Dominic Duggan, John Ophel · Journal of Functional Programming · 2002

Type classes are a novel combination of parametric polymorphism and constrained types. Although most implementations restrict type classes to be single-parameter, the generalization to multi-parameter type classes has gained increasing attention. A problem with multi-parameter type classes is the increased possibilities they introduce for ambiguity in inferred types, impacting their usefulness in many practical situations. A new type-checking strategy, domain-driven unifying resolution , is identified as an approach to solve these problems. Domain-driven unifying resolution is simple, efficient, and practically useful. However, even with severe restrictions on instance definitions, it is not possible to guarantee that type-checking with unifying resolution terminates. This is in contrast with the naive generalization of single parameter resolution strategies. Domain-driven unifying resolution is guaranteed to terminate if the type class constraints are satisfiable; however satisfiability is undecidable even with severe restrictions on instance definitions. These results shed some light on ambiguity problems with multi-parameter type classes.

Cited by 18Open access

Type classes in Haskell

Mark P. Jones · Cambridge University Press eBooks · 1994

This chapter expands on the implementation of type classes in Haskell using dictionary values as proposed by Wadler and Blott (1989) and sketched in Section 4.5. For brevity, we refer to this approach to the use of type classes as HTC. The main emphasis in this chapter is on concrete implementation and we adopt a less rigourous approach to formal properties of HTC than in previous chapters. In particular, we describe a number of optimisations that are necessary to obtain an efficient implementation of HTC - i.e. to minimise the cost of overloading. We do not consider the more general problems associated with the efficient implementation of non-strict functional languages like Haskell which are beyond the scope of this thesis.

Cited by 0

Type classes in Haskell

Cordelia Hall, Kevin Hammond, Simon Jones et al. · ACM Transactions on Programming Languages and Systems · 1996

This article defines a set of type inference rules for resolving overloading introduced by type classes, as used in the functional programming language Haskell. Programs including type classes are transformed into ones which may be typed by standard Hindley-Milner inference rules. In contrast to other work on type classes, the rules presented here relate directly to Haskell programs. An innovative aspect of this work is the use of second-order lambda calculus to record type information in the transformed program.

Cited by 248Open access

Existentially Quantified Type Classes

2008

Abstract We present a formal framework for existential types andtype classes. In contrast to L"aufer's original proposal our system includes multi-parameter type classes andfunctional dependencies etc. Our system is powerful enough to express guarded recursive data types, a recentextension of algebraic data types. Type inference in our extension becomes a hard problem. For this purpose,we introduce a novel constraint solver. In general, we lose the principal types property. However, we considerseveral classes for which we infer a principal type if one exists. Our extension has been implemented as part ofthe Chameleon system. 1 Introduction We start by reviewing L"aufer's and Odersky's [10] ex-tension of ML with existential types. We use Haskell (Chameleon) notation throughout. Example 1 Consider data KEY = forall a. Mk a (a->Int) g (Mk x f) = f x

Cited by 0

Type classes in Mercury

David W. Jeffery, Fergus Henderson, Zoltán Somogyi · 2000

The type systems of functional languages such as Haskell have recently become more powerful and expressive. They not only allow programmers to write code that works on values of any type (genericity), they also allow programmers to require that a particular type belongs to a given type class (constrained genericity). Such code may use any of the methods of the type class, since every type that is a member of the type class must implement those methods. This capability makes it significantly easier to express solutions to many common problems, and promotes code reuse. Incorporating type classes in a logic programming language provides some new challenges. In this paper, we explain how we have extended Mercury's type system to include support for type classes. We show that type classes integrate very nicely with Mercury's mode, determinism and uniqueness systems, and describe how our implementation works.

Cited by 17

Type Inference for Multi-Parameter Type Classes

Martin Sulzmann, Peter J. Stuckey · 2008

We observe that the combination of multi-parameter type classes with existential types and type annotations leads to a loss of principal types. As a consequence type inference in implementations such as GHC is incomplete. This may be a surprising fact for users of these standard features. We conduct a concise investigation of the problem and are able to precisely explain why we lose principality and completeness of inference. As remedy we propose several novel inference methods to retain completeness and principality.

Cited by 0

Semisimple classes and upper-type radical classes of narings

T. L. Jenkins, Daryl Kreiling · Proceedings of the American Mathematical Society · 1970

In the universal class of associative rings every class <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of rings determines a unique upper radical class. It is shown that the same result is valid in the universal class of alternative rings but is not necessarily true in the universal class of narings. The latter class does however determine a type of upper radical.

Cited by 2Open access

Boolean reflection via type classes

Benjamin Grégoire, E. ̃Tassi · HAL (Le Centre pour la Communication Scientifique Directe) · 2016

International audience

Cited by 1

Using Containers and Type Classes

Alejandro Serrano Mena · Apress eBooks · 2014

You have seen how parametric polymorphism and higher-order functions help in the process of abstraction. In this chapter, I’ll introduce a new kind of polymorphism that sits in between parametric and the absence of polymorphism: ad hoc polymorphism. Using this feature, you can express that certain types exhibit a common behavior. And incidentally, you will learn how Haskell makes it possible to use addition, (+), on different numeric types while maintaining a strong type system.

Cited by 0

Parametric type classes. Extended abstract

Chen, Kung, Hudak, Paul, Odersky, Martin · Repository KITopen (Karlsruhe Institute of Technology) · 1992

Cited by 2Open access

Using Containers and Type Classes

Alejandro Serrano Mena · Apress eBooks · 2019

You have seen how parametric polymorphism and higher-order functions help in the process of abstraction. In this chapter, I’ll introduce a new kind of polymorphism that sits in between parametric and the absence of polymorphism: ad hoc polymorphism. Using this feature, you can express that certain types exhibit a common behavior. Incidentally, you will also learn how Haskell makes it possible to use addition, (+), on different numeric types like Integer and Float while maintaining a strong type system.

Cited by 0