7 ms·
Please write a type for the following function: def compose(start, *args): def helper(x): for func in reversed(args): x = func(x) ret
by slaymaker1907 5y ago
Please write a type for the following function:
def compose(start, *args):
def helper(x):
for func in reversed(args):
x = func(x)
return start(x)
return helper
There is no mainstream typed language which can write a fully general type for the vararg compose function. TypeScript is probably the one that comes closest, but last I checked it still was unable to write a sufficiently powerful array type. You can write a type for a version of compose with a fixed number of arguments, but not for one working over an arbitrary number of arguments.
- tetha 5y agoAs I said, there are infinite possible programs that cannot be type checked statically. This is derived from the halting theorem trivially - lambda(p) = if p.halts() then A() else B(). However, the intersection of programs I encounter in practice with the number of programs that can be statically checked is rather large.
- phoneperson 5y agoYou are probably thinking of Gödel's incompleteness theorems. I do not think that you can trivially derive it from the halting problem.
- tehnub 5y agoHe just did derive it from the halting problem. In words: It's impossible to statically check the type of a function that takes a program P as its input, and returns the integer 1 as its output if P halts, and returns the string "1" if it does not halt. It would require solving the halting problem, which is undecidable.
- native_samples 5y agoHow does that follow? The input type would be vague, e.g. ByteArray or Program or something.
- tehnub 5y agoIt's the return type that isn't decidable. You can't statically check, in the arbitrary case, whether the function returns an int or a string.
- native_samples 5y agoNo, but that isn't required for a static type system. Most languages would just unify to the top type.
- tehnub 5y agoCould you elaborate on that? It sounds like I may have an overly simplified understanding of the topic here—wouldn't be the first time.
- native_samples 5y agoStatic type systems don't imply fully dependent types. In Kotlin: sealed class Program class HaltingProgram : Program() class InfiniteProgram : Program() fun checkIsHalting(p: ByteArray) = if (halts(p)) HaltingProgram() else InfiniteProgram() This program will type check just fine. The inferred return type will be Program because that's the nearest shared ancestor type of both possible return types. Good luck implementing the halts() function of course, but that's not the type system's problem.
- tetha 5y agoYes, but it is not required that a type system has a singular top type. It is entirely valid for a type system to have any number of types which are not in any sub- or supertype relationship. And once there are two types T1 and T2 which are neither subtypes, nor supertypes of each other, and 2 expressions A1 and A2 of types T1 and T2, and a statically undecideable expression p, then statically typing "if p then A else B" is a problem. And yes, I agree: Most if not all practical type systems will not accept an if-else statement if they cannot unify both branches of the conditional into a single type. Which makes sense. Because you have to act on the result of the expression, and then it needs to have some common type. But on a purely theoretical basis, it is entirely possible and valid to have an undecideable type system. Which, btw, happens for a lot of languages: https://3fx.ch/typing-is-hard.html https://3fx.ch/typing-is-hard.html . There are C++ programs which are provably impossible to type at compile time.
- phoneperson 5y agoThe theorems predate Turing's theorem. As for the halting problem, it is solvable with an oracle, unlike the incompleteness theorems.
- monocasa 5y agoI think you can in rust as long as args is a slice. Rust doesn't have varargs except for c interop. A slice or Vec of function pointers is the idiomatic way to do the same thing. Something like: fn compose<X, T>(start: Box<Fn(T) -> X>, args: Vec<Box<Fn(T) -> T>>) -> Fn(T) -> X { move |x: X| { let mut x = x; for func in args.iter(). reversed() { x = func(x); } start(x) } }
- slaymaker1907 5y agoThis only works if all of the functions return the same type. However, you can write a compose macro which operates as expected.
- loup-vaillant 5y agoVararg functions also have limited use. Especially considering that most of the time, your args will all have the same type, and therefore could just be passed in an array or similar. The one mainstream exception I know of is print functions, and we have* ways to statically check those. Your toy example, even generalised, has no practical use. If I can write this: compose(f, f1, f2, f3) Then I can write that instead (Haskell): f . f3 . f2 . f1 Or this (F#): f1 |- f2 |- f3 |- f And now we’ve reduced the problem to a simple function composition, which is very easy to define (Ocaml): let (|-) f g = fun x -> g (f x) (|-): (’a -> ’b) -> (’b -> ’c) -> (’a -> ’c) This generalises to any fold where the programmer would provide the list statically (as they always would for a vararg function): instead of trying to type the whole thing, just define & type the underlying binary operation.
- skrimp 5y agoThis still technically reduces the generality of the given function since you are specifying that each function cannot have multiple overloads. let f be a overload set matching the signatures {a -> b, i -> j} let g be a overload set matching the signatures {b -> c, j -> k} compose(g, f) could be given a to return c or i to return k
- loup-vaillant 5y ago> This still technically reduces the generality of the given function My point was that we are almost never hurt by that reduction. > you are specifying that each function cannot have multiple overloads Haskell has type classes, and if we restrict ourselves to local type inference it's fairly easy to have C++ style overloads without even that. So no, I'm not specifying such a thing.
- fiddlerwoaroof 5y ago> Vararg functions also have limited use. This is only because people are using statically typed language that place arbitrary restrictions on such functions and make them harder to use. In dynamically typed languages, vararg functions are widely used and enable patterns that are pretty nice.
- munificent 5y ago> There is no mainstream typed language which can write a fully general type for the vararg compose function. True. A more interesting question might be what level of static safety and performance benefits you'd be willing to sacrifice to be able to write functions like this. Personally, I don't find the kind of code I can't fit into static types particularly appealing, but I find the code navigation, error checking, and optimizations of static types to be priceless.
- albrewer 5y agoI took a stab at it, there's not enough information to figure out anything more specific: from typing import Callable, Any def compose(start: Callable[[Any], Any], *args: Callable[[Any], Any] -> Callable[[Any], Any]: def helper(x: Any) -> Any: for func in reversed(args): x = func(x) return start(x) return helper
- slaymaker1907 5y agoSure, that's probably as close as you can get, but ideally it would be possible to write a type which guarantees the input functions are compatible as well as knowing what the type is of the returned function.
- skrimp 5y agoC++ is an extremely mainstream language that can write a fully general version of compose with variable arguments. https://godbolt.org/z/h7n8Y7qf1 https://godbolt.org/z/h7n8Y7qf1 Like sure, you can't write out a type for the entire overload set. Overload sets don't have types, but functions do. However, I don't think you'd ever actually want to write out the type of the compose function. Instead, I think it would be more reasonable to request that every intermediate function call is type-checked with fully specified types. In C++ this is the case.
- Matheus28 5y agoGreat implementation of what the parent comment asked. Not only that, but the compiler managed remove all the abstractions. (very minor nitpick: I'd pick `auto&& x` over `auto x`)
- iamevn 5y agoI think you can get close implementing it as a macro in typed racket, expanding the type out based on how many arguments you give it. But then it's not a first class function until you expand it. Found this implementation which also provides pre-expanded forms that are first class functions for specific lengths of arguments docs: https://docs.racket-lang.org/typed-compose/index.html https://docs.racket-lang.org/typed-compose/index.html implementation: https://git.marvid.fr/scolobb/typed-compose/src/branch/master/main.rkt https://git.marvid.fr/scolobb/typed-compose/src/branch/maste...
- nybble41 5y agoThis is really a fairly trivial exercise in Haskell, provided you pass the arguments as a heterogeneous list—which is semantically equivalent to a variable argument list. Here is my implementation: https://gist.github.com/nybble41/c459c6927a3bad8ec350d227193ef637 https://gist.github.com/nybble41/c459c6927a3bad8ec350d227193... Here I defined a simple `Pipeline` GADT for the argument list, which is just a list of functions with some extra type constraints to ensure that they can be composed. You could do the same thing with a more general type like HList but the type signature for the `compose` function would be much more verbose since you would need to define the relationships between each pair of adjacent function types through explicit constraints involving type families, whereas the `Pipeline` type handles that internally. Perhaps you don't consider Haskell "mainstream" enough?