This talk presents evidence that humans learn complex functions by harnessing compositionality: complex structure is decomposed into simpler building blocks. I formalize this idea in the framework of Bayesian nonparametric regression using a grammar over Gaussian process kernels, and compare this approach with other structure learning approaches. People consistently chose compositional (over non-compositional) extrapolations and interpolations of functions. Experiments designed to elicit priors over functional patterns revealed an inductive bias for compositional structure. Compositional functions are perceived as subjectively more predictable than noncompositional functions, and exhibited other signatures of predictability, such as enhanced memorability. Taken together, these results support the view that the human intuitive theory of functions is inherently compositional.