Is it possible to cache a faceted search form?
There're various ways of doing this. The simplest would be to just use the submitted slugs to generate a new cache key for each different search, like Jamie suggests. This is a very straightforward and readable solution, which in most cases would probably yield a "good enough" performance boost. You'd simply create a key based on the params that are used in your cached content, so something like (could be made a bit less verbose if you prefer):

{% set submittedTypesArray = craft.request.getParam('type') %}
{% set submittedTypesString = submittedTypesArray | join('-') %}

{% cache using key "restaurant-filter-type-" ~ submittedTypesString %}
    {% set typeList = craft.categories.group('restaurantType') %}

    {% for type in typeList %}
        &lt;div class="field field--checkbox"&gt;
            &lt;input type="checkbox" name="type[]" id="{{ type.slug }}" value="{{ type.slug }}"{% if type.slug in submittedTypesArray %} checked{% endif %}&gt;
            &lt;label for="{{ type.slug }}"&gt;{{ type.title }}&lt;/label&gt;
        &lt;/div&gt;
    {% endfor %}
{% endcache %}


The backdraw of this solution is that it generates one cache entry for every different combination of the types. If this is "good enough" depends on your project. 

If you want to use the approach naboovalley describes in the linked answer, here is a rewrite for your usecase:

{% set typeCategories %}
    {% cache using key "restaurant-filter-type" %}
        {% set typeList = craft.categories.group('restaurantType') %}

        {% for type in typeList %}
            &lt;div class="field field--checkbox"&gt;
                &lt;input type="checkbox" name="type[]" id="{{ type.slug }}" value="{{ type.slug }}" data-type-{{ type.slug }}&gt;
                &lt;label for="{{ type.slug }}"&gt;{{ type.title }}&lt;/label&gt;
            &lt;/div&gt;
        {% endfor %}
    {% endcache %}
{% endset %}

{% set types = craft.request.getParam('type') %}    
{% for type in types %}
    {% set typeCategories = typeCategories | replace('data-type-' ~ type, 'checked')  %}
{% endfor %}

{{ typeCategories }}


It would be possible to do this with several category groups inside one variable/cache entry, but you'd have to give them different data-names to make sure that you don't run into problems if two categories in different groups have the same slug.

I'm sure there's a wicked elegant way to do the replace without the for loop, I just couldn't wrap my head around it right now. ;)

And, just to add more options, if this was a really high traffic site (or the server that hosts the site is really crappy), I'd actually update the status of the checkboxes with javascript on the client, instead of doing it with Craft. Even though it would maybe annoy a user that has javascript turned off and has to check all the checkboxes for every search, nothing would break. And you can't beat the performance of doing something on the client instead of on the server.